Codeforces Round #263 (Div. 2) D. Appleman and Tree 树形dp _Codeforces

不飞则已，一飞冲天；不鸣则已，一鸣惊人。这篇文章主要讲述Codeforces Round #263 (Div. 2) D. Appleman and Tree 树形dp相关的知识，希望能为你提供帮助。
链接：http://codeforces.com/contest/462/problem/D
题意：给定n个点的树，
0为根，下面n-1行表示每个点的父节点
最后一行n个数表示每个点的颜色，0为白色，1为黑色。
把树分成若干个联通块使得每个联通块有且仅有一个黑点，问有多少种分法（结果mod1e9+7）
题解：树形dp，每个点有2个状态，已经归属于某个黑点和未归属于某个黑点。
代码：

31 int n; 32 int x[MAXN]; 33 VI G[MAXN]; 34 ll dp[MAXN][2]; 35 36 void dfs(int u) { 37if (x[u]) dp[u][1] = 1; 38else dp[u][0] = 1; 39rep(i, 0, G[u].size()) { 40int v = G[u][i]; 41dfs(v); 42ll old[2] = { dp[u][0], dp[u][1] }; 43dp[u][0] = (old[0] * dp[v][1] + old[0] * dp[v][0]) % MOD; 44dp[u][1] = (old[1] * dp[v][1] + old[1] * dp[v][0] + old[0] * dp[v][1]) % MOD; 45} 46 } 47 48 int main() { 49ios::sync_with_stdio(false), cin.tie(0); 50cin > > n; 51rep(i, 1, n) { 52int p; 53cin > > p; 54G[p].pb(i); 55} 56rep(i, 0, n) cin > > x[i]; 57dfs(0); 58cout < < dp[0][1] < < endl; 59return 0; 60 }

【Codeforces Round #263 (Div. 2) D. Appleman and Tree 树形dp】