Solution
比较明显的树形DP模型。
首先可以先用一次DFS求出以1为根时，sum[i]（以i为子树的根时，满足要求的子树的个数）。
考虑将根从i变换到它的儿子j时，sum[i]产生的变化.
在变化前sum[i]不为0时,可以用求逆元的方法求出新的sum[i].
sum[i]为0时,就需要遍历i的新的儿子.
官方的题解给出了一个比较好的做法是预处理i的儿子的前缀积,和后缀积.使用的时候只要去除相应的儿子.
#include <bits/stdc++.h>
#define LL long long
using namespace std; const int N = ;
const int MOD = int (1e9 + ); struct edge {
int v, ne;
} E[N << ];
int head[N], cnt; LL sum[N], ans[N]; int n; LL Quikpower (LL Base, LL Power)
{
LL k = ;
while ( Power > ) {
if (Power & ) k = (k * Base) % MOD;
Base = (Base * Base) % MOD;
Power >>= ;
}
return k;
} inline void add (int u, int v)
{
E[++cnt].v = v, E[cnt].ne = head[u];
head[u] = cnt;
} void dfs (int u, int from)
{
sum[u] = ;
for (int i = head[u]; i; i = E[i].ne) {
int v = E[i].v;
if (v != from) {
dfs (v, u);
sum[u] = sum[u] * sum[v] % MOD;
}
}
if (from != ) ++sum[u];
} void dfs2 (int u, int from)
{
LL tem = ;
if (ans[from] != ) {
tem = ans[from] * Quikpower (sum[u], MOD - ) % MOD + ;
}
else {
for (int i = head[from]; i; i = E[i].ne) {
int v = E[i].v;
if (v != u)
tem = tem * sum[v] % MOD;
}
tem++;
}
sum[from] = tem;
LL k = ;
for (int i = head[u]; i; i = E[i].ne) {
int v = E[i].v;
k = k * sum[v] % MOD;
}
ans[u] = k; int reset = sum[u];
for (int i = head[u]; i; i = E[i].ne) {
int v = E[i].v;
if (v != from) {
dfs2 (v, u);
sum[u] = reset;
}
}
}
int main()
{
ios::sync_with_stdio (); cin >> n;
for (int i = , x; i <= n; i++) {
cin >> x;
add (i, x), add (x, i);
} dfs (, ); dfs2 (, ); for (int i = ; i <= n; i++)
cout << (ans[i] + MOD) % MOD << " ";
}