题目链接：http://codeforces.com/contest/543/problem/D
给你一棵树，初始所有的边都是坏的，要你修复若干边。指定一个root，所有的点到root最多只有一个坏边。以每个点为root，问分别有多少种方案数。
dp[i]表示以i为子树的root的情况数，不考虑父节点，考虑子节点。 dp[i] = dp[i] * (dp[i->son] + 1)
up[i]表示以i为子树的root的情况数(倒着的)，考虑父节点，不考虑子节点。 这里需要逆元。 注意(a/b)%mod中b%mod=0是错误的，所以要特殊判断。
//#pragma comment(linker, "/STACK:102400000, 102400000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair <int, int> P;
const int N = 2e5 + ;
LL dp[N], mod = 1e9 + , up[N];
vector <int> edge[N];
int cnt[N]; //子树(dp[i->son] + 1)%mod != 0的节点数
LL fuck[N]; //子树(dp[i-son] + 1)%mod != 0的方案数相乘 LL fpow(LL a, LL n) {
LL res = ;
while(n) {
if(n & )
res = res * a % mod;
a = a * a % mod;
n >>= ;
}
return res;
} void dfs1(int u, int p) {
dp[u] = ;
fuck[u] = ;
for(int i = ; i < edge[u].size(); ++i) {
int v = edge[u][i];
if(v == p)
continue;
dfs1(v, u);
if(dp[v] + == mod)
cnt[u]++;
else
fuck[u] = ( + dp[v]) % mod * fuck[u] % mod;
dp[u] = ( + dp[v]) % mod * dp[u] % mod;
}
} void dfs2(int u, int p) {
for(int i = ; i < edge[u].size(); ++i) {
int v = edge[u][i];
if(v == p)
continue;
//LL temp = dp[u] * fpow((dp[v] + 1) % mod, mod - 2) % mod; //error
LL temp = ;
if(dp[v] + == mod && up[u] && cnt[u] == ) { //特殊情况
temp = fuck[u];
} else {
temp = dp[u] * fpow((dp[v] + ) % mod, mod - ) % mod;
}
up[v] = (up[u] * temp % mod + ) % mod;
dfs2(v, u);
}
} int main()
{
int n, u;
scanf("%d", &n);
for(int i = ; i <= n; ++i) {
scanf("%d", &u);
edge[i].push_back(u);
edge[u].push_back(i);
}
dfs1(, -);
up[] = ;
dfs2(, -);
for(int i = ; i <= n; ++i) {
printf("%lld%c", dp[i]*up[i]%mod, i == n ? '\n': ' ');
}
return ;
}