半夜 12:00 我不睡觉来这里更文章来了。。。
这次的甲组好简单,第一次 $AK$ 了,
这题看上去很难,要求什么不挨边,其实分析一下就是 树形 $DP$。
首先要求不挨边,所以我们需要每个点选不选的状态,那么设 $f[i][0/1]$
为以 $i$ 为根的子树,$i$ 选或者不选的方案数。
如果 $i$ 选,那么儿子就不能选,否则儿子选不选无所谓。
乘起来就好了,我用的 $dfsdp$,在算好儿子后直接加父亲,节约了点码量。
代码:
#include <vector> #include <iostream> #define int long long using namespace std; int n, mod = 1000000007; int p[200005], f[200005][2]; vector <int> v[200005]; int dfs (int x) { f[x][0] = f[x][1] = 1; for (int i = 0;i < v[x].size (); i ++) dfs (v[x][i]); -- f[x][0]; f[p[x] ][0] = f[p[x] ][0] * (f[x][1] + f[x][0] + 1) % mod; f[p[x] ][1] = f[p[x] ][1] * (f[x][0] + 1) % mod; return (f[x][0] + f[x][1] + 1) % mod; } signed main () { cin >> n; for (int i = 2; i <= n; i ++) { cin >> p[i]; v[p[i] ].push_back (i); } cout << dfs (1); return 0; }
标签:YACS,挨边,200005,int,题解,甲组,mod From: https://www.cnblogs.com/Xy-top/p/17113103.html