题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5647
题解：
令dp[u][0]表示u所在的子树中所有的包含i的集合数,设u的儿子为vi，则易知dp[u][0]=(dp[v1][0]+1)*...*(dp[vk][0]+1)。
令dp[u][1]表示u所在的子树中所有的包含i的集合数的大小的和，则有dp[u][1]=dp[u][1]*(dp[v][0]+1)+dp[v][1]*dp[u][0]；
其中dp[u][1]*(dp[v][0]+1)表示新引入v的（dp[v][0]+1）个组合的时候，左边已知的贡献值（dp[u][1]，即已知的包含节点i的集合数的大小的和）增倍之后的量。
dp[v][1]*dp[u][0]则与上面刚好反过来，考虑对于已知的dp[u][0]种集合数，儿子v的贡献值增倍后的量。
则最后的答案为dp[1][1]+...+dp[n][1]
ps: 如果还不明白dp[u][0],dp[u][1]表示的含义，可以用代码跑一下简单的样例，把它们都打印出来，应该会好理解一些。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; const int maxn = 2e5 + ;
const int mod = 1e9 + ;
typedef long long LL; struct Edge {
int v, ne;
Edge(int v, int ne) :v(v), ne(ne) {}
Edge() {}
}egs[maxn]; int head[maxn], tot;
int n; void addEdge(int u, int v) {
egs[tot] = Edge(v, head[u]);
head[u] = tot++;
} LL dp[maxn][]; void solve(int u) {
dp[u][] = dp[u][] = ;
int p = head[u];
while (p != -) {
Edge& e = egs[p];
solve(e.v);
dp[u][] = (dp[u][] * (dp[e.v][] + ) + dp[e.v][] * dp[u][]) % mod;
dp[u][] = dp[u][] * (dp[e.v][] + )%mod;
p = e.ne;
}
} void init() {
memset(head, -, sizeof(head));
tot = ;
} int main() {
int tc;
scanf("%d", &tc);
while (tc--) {
init();
scanf("%d", &n);
for (int i = ; i <= n; i++) {
int v;
scanf("%d", &v);
addEdge(v, i);
}
solve();
LL ans = ;
for (int i = ; i <= n; i++) {
//printf("dp[%d][1]:%d\n", i,dp[i][1]);
ans += dp[i][];
ans %= mod;
}
printf("%lld\n", ans);
}
return ;
} /*
1 //testcase
3
1
1
*/
以下是按官方题解的思路写的代码，但是wa了，当(dp[u]+1)%mod==0的时候逆元就求不出来了。
这样写就t了，说明数据确实会出现这种情况
官方题解：
#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long LL; const int maxn = 2e5 + ;
const int mod = 1e9 + ; struct Edge {
int v, ne;
Edge(int v,int ne):v(v),ne(ne){}
Edge(){}
}egs[maxn*]; int head[maxn], tot; void addEdge(int u, int v) {
egs[tot] = Edge(v, head[u]);
head[u] = tot++;
} void gcd(LL a, LL b, LL &d, LL &x, LL &y) {
if (!b) { d = a; x = ; y = ; }
else { gcd(b, a%b, d, y, x); y -= x*(a / b); }
// x = (x%mod + mod) % mod;
// y = (y%mod + mod) % mod;
} LL invMod(LL a, LL b) {
LL d, x, y;
gcd(a, b, d, x, y);
return (x%mod+mod)%mod;
} int n;
LL dp[maxn];
int fa[maxn];
//自底向上
void dfs1(int u) {
dp[u] = ;
int p = head[u];
while (p != -) {
Edge& e = egs[p];
dfs1(e.v);
dp[u] *= (dp[e.v] + ); dp[u] %= mod;
p = e.ne;
}
}
//自顶向下
void dfs2(int u) {
if (fa[u]) {
LL tmp = dp[fa[u]] * invMod(dp[u] + , (LL)mod) % mod;
dp[u] = dp[u] * (tmp + ) % mod;
}
int p = head[u];
while(p != -) {
Edge& e = egs[p];
dfs2(e.v);
p = e.ne;
}
} void init() {
fa[] = ;
memset(dp, , sizeof(dp));
memset(head, -, sizeof(head));
tot = ;
} int main() {
// freopen("data_in.txt", "r", stdin);
int tc;
scanf("%d", &tc);
while (tc--) {
scanf("%d", &n);
init();
for (int i = ; i <= n; i++) {
int x;
scanf("%d", &x);
addEdge(x, i);
fa[i] = x;
}
dfs1();
dfs2();
LL ans = ;
for (int i = ; i <= n; i++) {
ans += dp[i]; ans %= mod;
}
printf("%lld\n", ans);
}
return ;
}
/*
*/
但是！这种情况比较特殊，是可以单独处理一下的，对于节点u，如果在第一次dfs中它的儿子中有(dp[v]+1)%mod==0,那么说明在第一次dfs中dp[u]=0，也就是说dp[u]+1==1，u对它的父亲是没有贡献的！，那么在第二次dfs中，dp[u]实际保存的数就是整颗树中不包含u这颗子树的所有节点中包含u的父亲的集合的个数，所以只要算(dp[u]+1)*spec（spec表示v所有的兄弟的（dp[vi]+1)的乘积，不包含v本身），就可以了,具体看代码。
#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long LL; const int maxn = 2e5 + ;
const int mod = 1e9 + ; struct Edge {
int v, ne;
Edge(int v,int ne):v(v),ne(ne){}
Edge(){}
}egs[maxn*]; int head[maxn], tot; void addEdge(int u, int v) {
egs[tot] = Edge(v, head[u]);
head[u] = tot++;
} void gcd(LL a, LL b, LL &d, LL &x, LL &y) {
if (!b) { d = a; x = ; y = ; }
else { gcd(b, a%b, d, y, x); y -= x*(a / b); }
}
LL invMod(LL a, LL b) {
LL d, x, y;
gcd(a, b, d, x, y);
return (x%mod+mod)%mod;
} int n;
LL dp[maxn];
int fa[maxn]; void dfs1(int u) {
dp[u] = ;
int p = head[u];
while (p != -) {
Edge& e = egs[p];
dfs1(e.v);
dp[u] *= (dp[e.v] + ); dp[u] %= mod;
p = e.ne;
}
} void dfs2(int u,LL spec) {
if (fa[u]) {
LL tmp;
if((dp[u]+)%mod)
tmp=dp[fa[u]] * invMod(dp[u] + , mod) % mod;
else {
tmp = (dp[fa[u]]+) * spec % mod;
}
dp[u] = dp[u] * (tmp + ) % mod;
}
int p = head[u]; spec = ;
int po = -,flag=;
while(p != -) {
Edge& e = egs[p];
if ((dp[e.v] + ) % mod == ) {
if(po==-) po = e.v;
else {
flag = ;
dfs2(e.v, );
}
}
else {
spec *= (dp[e.v] + ); spec %= mod;
dfs2(e.v, spec);
}
p = e.ne;
}
if (po!=-) {
if (!flag) dfs2(po, spec);
else dfs2(po, );
}
} void init() {
fa[] = ;
memset(dp, , sizeof(dp));
memset(head, -, sizeof(head));
tot = ;
} int main() {
//freopen("data_in.txt", "r", stdin);
int tc;
scanf("%d", &tc);
while (tc--) {
scanf("%d", &n);
init();
for (int i = ; i <= n; i++) {
int x;
scanf("%d", &x);
addEdge(x, i);
fa[i] = x;
}
dfs1();
dfs2(,);
LL ans = ;
for (int i = ; i <= n; i++) {
ans += dp[i]; ans %= mod;
}
printf("%lld\n", ans);
}
return ;
}
/* */