【CF1146F】Leaf Partition

发布时间 2023-07-02 15:00:22作者: Custlo

这个题还是蛮有趣的,其实弄清楚这个染色的方案,这个题还是简单的。

本质上只是对于考虑对于连通块染色,但是带有一些限制。

所以我们考虑在 LCA 上拼接若干条根到叶子的路径。

那我们就可以依据这一想法来设计状态。

第一是这个点没有染色,那我们记这一状态为 \(h\)

第二是这个点连接着一条到一个叶子的链,值得注意,这种情况不符合最小联通图的定义,所以不可以作为一个根来算答案,要一直连到祖先上,记为 \(f\)

第三是拼接了至少两条同色的到叶子的链,记为 \(g\)

考虑依次插入 \(v\) 这个子节点的答案,那么转移就很明显了:

首先是如果不染,那么这个点可以随便算,但是注意不能算 \(f\) 这种不合法的答案。

\[h_u = \prod(h_v + g_v) \]

如果只染一条链,那么可以从无色染到有,也可以原本有色,不进行拼接。

\[f_u = f_u \times (g_v + h_v) + h_u \times (g_v + f_v) \]

如果是染了至少两条链,那就可由一个一条或者多条的连上来,或者随便算一下儿子。

\[g_u = g_u \times (f_v + 2 \times g_v + h_v) + f_u \times (g_v + f_v) \]

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
#define lc u << 1
#define rc u << 1 | 1
#define int long long
// g -> f -> h 
using namespace std;

const int N = 2e5 + 5, mod = 998244353;

vector <int> e[N];
int n, g[N], h[N], f[N];

void dp (int u) {
	if (! e[u].size()) { g[u] = 1; return ; }
	h[u] = 1;
	for (int v : e[u]) {
		dp(v);
		g[u] = g[u] * (f[v] + 2 * g[v] + h[v]) + f[u] * (g[v] + f[v]);
		f[u] = f[u] * (g[v] + h[v]) + h[u] * (g[v] + f[v]);
		h[u] = h[u] * (h[v] + g[v]);
		g[u] %= mod, f[u] %= mod, h[u] %= mod;
	}
}
signed main () {
	ios :: sync_with_stdio(0);
	cin >> n;
	for (int i = 2, fa; i <= n; i ++)
		cin >> fa, e[fa].push_back(i);
	dp(1), cout << (g[1] + h[1]) % mod;
	return 0;
}