题意：
有一颗树，每条边是好边或者是坏边，对于一个节点为x，如果任意一个点到x的路径上的坏边不超过1条，那么这样的方案是合法的，求所有合法的方案数。
对于n个所有可能的x，输出n个答案。
分析：
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 const int maxn = 200000 + 10; 9 const int MOD = 1000000007;10 int n;11 12 vector G[maxn], pre[maxn], suf[maxn];13 14 void scan(int& x)15 {16 x = 0;17 char c = ' ';18 while(c < '0' || c > '9') c = getchar();19 while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }20 }21 22 int d[maxn], f[maxn];23 24 void mul(int& x, int y) { x = 1LL * x * y % MOD; }25 26 void dfs(int u)27 {28 d[u] = 1;29 int sz = G[u].size();30 for(int i = 0; i < sz; i++)31 {32 int v = G[u][i];33 dfs(v);34 mul(d[u], d[v] + 1);35 }36 37 int p = 1, s = 1;38 for(int i = 0; i < sz; i++)39 {40 mul(p, d[G[u][i]] + 1);41 mul(s, d[G[u][sz-1-i]] + 1);42 pre[u].push_back(p);43 suf[u].push_back(s);44 }45 46 reverse(suf[u].begin(), suf[u].end());47 }48 49 void dfs2(int u)50 {51 int sz = G[u].size();52 for(int i = 0; i < sz; i++)53 {54 int v = G[u][i];55 f[v] = f[u];56 if(i > 0) mul(f[v], pre[u][i - 1]);57 if(i < sz - 1) mul(f[v], suf[u][i + 1]);58 f[v]++;59 if(f[v] >= MOD) f[v] -= MOD;60 dfs2(v);61 }62 }63 64 int main()65 {66 scanf("%d", &n);67 for(int x, i = 2; i <= n; i++)68 {69 scan(x);70 G[x].push_back(i);71 }72 73 dfs(1);74 f[1] = 1;75 dfs2(1);76 77 for(int i = 1; i <= n; i++) printf("%I64d ", 1LL * d[i] * f[i] % MOD);78 79 return 0;80 }