题目链接：点击打开链接
题意：
给定n个点的树，
0为根，下面n-1行表示每个点的父节点
最后一行n个数 表示每个点的颜色，0为白色，1为黑色。
把树分成若干个联通块使得每个联通块有且仅有一个黑点，问有多少种分法（结果mod1e9+7）
思路：
树形dp，每个点有2个状态，已经归属于某个黑点和未归属于某个黑点。
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
#define N 300100
#define mod 1000000007
typedef long long ll;
ll dp[N][2];
//dp[i][1]表示i点已经归属于某个黑点的方法数
//dp[i][0]表示i点未曾归属某个黑点的方法数
int n, col[N];
vector<int>G[N];
void dfs(int u){
dp[u][1] = col[u];
dp[u][0] = col[u]^1;
for(int i = 0; i < G[u].size(); i++){
int v = G[u][i];
dfs(v);
ll old[2] = {dp[u][0], dp[u][1]};
dp[u][0] = (old[0]*dp[v][1] +old[0]*dp[v][0])%mod;
dp[u][1] = (old[1]*dp[v][1] +old[1]*dp[v][0] +old[0]*dp[v][1])%mod;
}
}
int main() {
int i, j;
while(~ scanf("%d",&n)){
for(i = 0; i < n; i++)G[i].clear();
for(i = 1; i < n; i++){
scanf("%d",&j);
G[j].push_back(i);
}
for(i = 0; i < n; i++)scanf("%d",&col[i]);
dfs(0);
cout<<dp[0][1]<<endl;
}
return 0;
}
/*
5
0 1 1 2
1 0 0 1 1
*/
Codeforces 462D Appleman and Tree 树形dp
原文：http://blog.csdn.net/qq574857122/article/details/38948259