题解：P12844 [蓝桥杯 2025 国 A] 树
ShwStone
·
·
题解
给一个状态设计极简的题解：
记 f_{i,0/1} 表示 i 选或者不选，子树内的方案数。
这个时间复杂度也是对的，因为每个点只有一个爷爷，所以这一步统计总共是 $\mathcal O(n)$ 的。
对于 $f_{i,0}$，儿子可选可不选。但是，因为兄弟之间的距离为 2，所以**至多选一个儿子**。
那就用经典技巧：维护 $f_{\text{son},0}$ 的前缀积和后缀积，如果选取第 $k$ 个儿子，就把 $f_{k,1}$ 和 $k-1$ 前缀、$k+1$ 后缀拼起来。
也可以用逆元处理，但是参考 ICPC 成都，说不定树状 DP 卡零逆元呢。
代码如下：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN(3e5 + 5);
const long long MOD(998244353);
int n;
vector<int> tree[MAXN];
long long dp[MAXN][2];
long long ll[MAXN], rr[MAXN];
void dfs(int u, int f) {
dp[u][1] = 1;
int cnt = 0;
for (int v : tree[u]) {
if (v == f) continue;
dfs(v, u);
}
for (int v : tree[u]) {
if (v == f) continue;
for (int w : tree[v]) {
if (w == u) continue;
(dp[u][1] *= dp[w][0]) %= MOD;
}
}
for (int v : tree[u]) {
if (v == f) continue;
cnt++;
ll[cnt] = rr[cnt] = dp[v][0];
}
ll[0] = rr[cnt + 1] = 1;
for (int i = 1; i <= cnt; i++) {
ll[i] = (ll[i - 1] * ll[i]) % MOD;
}
for (int i = cnt; i >= 1; i--) {
rr[i] = (rr[i + 1] * rr[i]) % MOD;
}
dp[u][0] = ll[cnt];
int id = 0;
for (int v : tree[u]) {
if (v == f) continue;
id++;
(dp[u][0] += (dp[v][1] * ll[id - 1] % MOD * rr[id + 1]) % MOD) %= MOD;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
dfs(1, 0);
cout << (dp[1][0] + dp[1][1] + MOD - 1) % MOD << endl;
return 0;
}
```
另：我考完用 Copilot 辅助复现了我的代码，结果神人 Copilot 不会写后缀积，写了这么依托：
```cpp
rr[i] = rr[i + 1] * ll[i] % MOD;
```
挂的只剩 30 分。吓我一跳。现在开始后怕，感觉考场上可能会挂一些莫名其妙的分。