【DP】 Codeforces Round #302 (Div. 1) D - Road Improvement

간단한 나무형 dp, 이동은 dp[i]=dp[i]*(dp[j]+1)이다. 그 중에서 j는 i의 하위 노드이고 잎 노드는 1이다.그러나 뿌리를 바꿀 때 역원을 사용할 수 없도록 주의해야 한다. 왜냐하면 방안 수가 0이 될 수 없기 때문이다. 그러나 모형을 뽑을 때 0이 나타날 수 있지만 뿌리를 바꿀 때 역원을 사용하는 것은 틀렸다.뿌리를 바꿀 때 인접표를 하나 더 켤 수밖에 없어요, 제발...

#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <math.h>
#include <time.h>
#define maxn 200005
#define maxm 400005
#define eps 1e-7
#define mod 1000000007
#define INF 0x3f3f3f3f
#define PI (acos(-1.0))
#define lowbit(x) (x&(-x))
#define mp make_pair
#define ls o<<1
#define rs o<<1 | 1
#define lson o<<1, L, mid 
#define rson o<<1 | 1, mid+1, R
#define pii pair<int, int>
#pragma comment(linker, "/STACK:16777216")
typedef long long LL;
typedef unsigned long long ULL;
//typedef int LL;
using namespace std;
LL qpow(LL a, LL b){LL res=1,base=a;while(b){if(b%2)res=res*base;base=base*base;b/=2;}return res;}
LL powmod(LL a, LL b){LL res=1,base=a;while(b){if(b%2)res=res*base%mod;base=base*base%mod;b/=2;}return res;}
//head

vector<LL> pre[maxn], suf[maxn];
vector<int> g[maxn];
LL res[maxn];
LL dp[maxn];
int n;

void read()
{
	int x;
	scanf("%d", &n);
	for(int i = 2; i <= n; i++) {
		scanf("%d", &x);
		g[x].push_back(i);
	}
}

void dfs(int u)
{
	int size = g[u].size();
	dp[u] = 1;
	for(int i = 0; i < size; i++) {
		dfs(g[u][i]);
		dp[u] = dp[u] * (dp[g[u][i]] + 1) % mod;
	}
	
	LL res1 = 1, res2 = 1;
	for(int i = 0; i < size; i++) {
		res1 = res1 * (dp[g[u][i]] + 1) % mod;
		res2 = res2 * (dp[g[u][size - i - 1]] + 1) % mod;
		pre[u].push_back(res1);
		suf[u].push_back(res2);
	}
	reverse(suf[u].begin(), suf[u].end());
}

void DFS(int u, LL pa)
{
	int size = g[u].size();
	res[u] = (pa + 1) * dp[u] % mod;
	for(int i = 0; i < size; i++) {
		LL t = (pa + 1);
		if(i) t = t * pre[u][i-1] % mod;
		if(i != size - 1) t = t * suf[u][i+1] % mod;
		DFS(g[u][i], t);
	}
}

void work()
{
	dfs(1);
	DFS(1, 0);
	for(int i = 1; i <= n; i++) printf("%lld%c", res[i], i == n ? '
' : ' ');
}

int main()
{
	read();
	work();
	
	return 0;
}