这个题还是蛮有趣的,其实弄清楚这个染色的方案,这个题还是简单的。
本质上只是对于考虑对于连通块染色,但是带有一些限制。
所以我们考虑在 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;
}
标签:Leaf,int,Partition,times,fa,拼接,CF1146F,dp,mod
From: https://www.cnblogs.com/Custlo/p/17520809.html