题目描述
http://codeforces.com/problemset/problem/1146/F
简要题意：给定一棵以 $1$ 为根的有根树，设 $L$ 为一个叶子节点的集合，$f(L)$ 就是这些叶子节点的最小连通子图，现在要求将所有叶子节点划分成若干个集合，使得任意两个叶子结合 $S$ 和 $T$ 满足 $f(S)\cap f(T)=\empty$，求方案数 $998244353$ 取模
$n\le 2\times 10^5$
Solution
我们定义 $f[u]$ 表示 $u$ 向下直连一棵染色的子树，注意 $u$ 本身不属于这棵被染色的子树
$g[u]$ 表示 $u$ 是一棵染色的子树的根，$h[u]$ 表示 $u$ 没有被染色
更新如下，注意更新顺序
1
2
3
| g[u] = (g[u] * (f[v] + 2 * g[v] + h[v]) + f[u] * (f[v] + g[v])) % p;
f[u] = (f[u] * (h[v] + g[v]) + h[u] * (f[v] + g[v])) % p;
h[u] = h[u] * (h[v] + g[v]) % p;
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <iostream>
#define maxn 200010
#define ll long long
using namespace std;
const int p = 998244353;
int n;
struct Edge {
int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}
ll f[maxn], g[maxn], h[maxn];
void dfs(int u, int fa) {
bool F = 0;
h[u] = 1;
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa) continue;
F = 1; dfs(v, u);
g[u] = (g[u] * (f[v] + 2 * g[v] + h[v]) + f[u] * (f[v] + g[v])) % p;
f[u] = (f[u] * (h[v] + g[v]) + h[u] * (f[v] + g[v])) % p;
h[u] = h[u] * (h[v] + g[v]) % p;
}
if (!F) g[u] = 1, f[u] = h[u] = 0;
}
int main() { fill(head, head + maxn, -1);
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 2; i <= n; ++i) {
int x; cin >> x;
add_edge(x, i);
} dfs(1, 0); cout << (g[1] + h[1]) % p << "\n";
return 0;
}
|