CF1146F Leaf Partition 题解
一道优秀的树形 \(\text{dp}\) 题目。
题意
首先简化一下题意。
求的是一颗有根树的连通块划分方案。
思路
观察题目，由于要统计方案，所以很容易确定是树形 \(\text{dp}\) 题目。
但树形 \(\text{dp}\) 的式子还是值得思考一下的。
我们可以设 \(f_{x,0}\) 表示与父亲相连的方案数，\(f_{x,1}\) 表示不与父亲相连的方案数。
这样还是无法快速转移。
我们可以再设 \(g_{x,0}\) 表示与 \(0\) 个儿子相连。
\(g_{x,1}\) 表示与 \(1\) 个儿子相连。
\(g_{x,2}\) 表示与 \(2\) 个儿子相连。
我们会发现，没有与儿子相连的点，必然不会在连通块内，所以必须不与父亲相连。
而只与一个儿子相连的点那么必然要与父亲相连，因为下面的叶子节点肯定会对应其他子树中的一个叶子节点。
而有两个儿子以上的点则可以随意。
所以：
\[f_{x,0}=(g_{x,0}+g_{x,2}) \]\[f_{x,1}=(g_{x,1}+g_{x,2}) \]此时，\(\text{dp}\) 就能进行转移了。
复杂度：\(O(n)\)
Code
#include
#define int long long
using namespace std;
const int maxn = 200010;
const int mod = 998244353;
int n , f[maxn][2] , g[3];
/*
f[i][1] 与父亲相连
f[i][0] 不与父亲相连。
g[0] 合并0个儿子 g[1] 合并1个儿子 g[2] 合并2个儿子
*/
vector son[maxn];
inline int read()
{
int asd = 0 , qwe = 1; char zxc;
while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
return asd * qwe;
}
signed main()
{
n = read() ;
for(int i = 2;i <= n;i++) son[read()].push_back(i);
for(int i = n;i >= 1;i--)
{
if(son[i].empty()) f[i][1] = f[i][0] = 1;
else
{
int g0 = 1 , g1 = 0 , g2 = 0;
for(auto j : son[i])
g[0] = g0 * f[j][0],
g[1] = g0 * f[j][1] + g1 * f[j][0],
g[2] = g1 * f[j][1] + g2 * f[j][0] + g2 * f[j][1],
g[0] %= mod , g[1] %= mod , g[2] %= mod,
g0 = g[0] , g1 = g[1] , g2 = g[2];
f[i][0] = (g[0] + g[2]) % mod , f[i][1] = (g[1] + g[2]) % mod;
}
}
cout << f[1][0];
return 0;
}