题目链接：http://codeforces.com/contest/461/problem/B
题目大意：
给定一课树，树上的节点有黑的也有白的，有这样一种分割树的方案，分割后每个子图只含有一个黑色节点，问这样的分割方案一共有多少种？
分析：
先定义3个函数（为了之后说起来方便）：
设A(x) = 在以顶点x为根的子树中，所有满足使x所在子图不含黑色顶点，其余子图只含有1个黑色顶点的分割方案种数 。
设B(x) = 在以顶点x为根的子树中，所有满足每个子图只含有1个黑色顶点的分割方案种数 。
设C(x) = 在以顶点x为根的子树中，所有满足使x所在子图只含有1个黑色顶点，其余子图只含有1个黑色顶点的分割方案种数 。
设B(x) = 在以顶点x为根的子树中，所有满足每个子图只含有1个黑色顶点的分割方案种数 。
设C(x) = 在以顶点x为根的子树中，所有满足使x所在子图只含有1个黑色顶点，其余子图只含有1个黑色顶点的分割方案种数 。
显然B(x) = C(x)
首先我们关注某一课子树的根节点，不妨设为rt，有2种情况：
不妨设rt有a个黑色的孩子节点，b个白色的孩子节点，rt的第i个黑色节点表示为rtBi，白色节点表示为rtWi，rt的第i个孩子节点表示为soni
1：color[rt] == BLACK
初始条件下B(rt) = 1，自己自身算一个
在这种情况下，rt一定不能与黑色的孩子节点相连，根据乘法原则，黑色节点部分的贡献为
；对于白色节点，先单看第i个，对于rt来说，有2种策略，一是不相连，二是相连，如果不相连，这个白色节点就和黑色节点一样了，贡献为B(rtWi)；如果相连，那么rt要连到没有黑色节点的部分，这样的方案数有A(rtWi)种，因此单个白色节点的贡献为A(rtWi) + B(rtWi)，所有白色节点的贡献就为 
。最终B(rt) = B(rt) * AllB * AllW（根节点把子树分成了不同的部分且互不影响，每个部分有多少种，全部乘起来就是了）。
2 : color[rt] == WHITE
初始条件下B(rt) = 0
在这种情况下，rt与每个孩子节点都有相连与不相连2种策略，对于soni，不相连的贡献自然是B(soni)，而相连的贡献就不是独立的了，很可能有跨越根节点到其他子树的方案，也就是说，对于每一棵子树，都要和其他每一棵子树有深入交流，乘法原则不适用了。
我们可以考虑增而治之，设rtSonsi为以rt为根节点，只拥有前i个孩子节点的树，A(rt)，B(rt)，C(rt)为相应数值，初始状态为A(rt) = 1，B(rt) = 0，C(rt) = 0，我们只要考虑soni+1加入时，A(rt)，B(rt)，C(rt)会如何变化，当子树全部加入时，就算完了。这里有2种情况：
（1）与soni+1相连：B(rt) = C(rt) = A(rt) * C(soni+1) + C(rt) * A(soni+1)
A(rt) = A(rt) * A(soni+1)
（2）与soni+1不相连：B(rt) = C(rt) = C(rt) * C(soni+1)
A(rt) = A(rt) * C(soni+1)
于是总变化为：B(rt) = C(rt) = A(rt) * C(soni+1) + C(rt) * [A(soni+1) + C(soni+1)]
A(rt) = A(rt) * [A(soni+1) + C(soni+1)]
一个优化：对于color[rt] == BLACK的情况，如果我们把rt看成是白色的，然后照此计算出A(rt)，B(rt)，C(rt)，那么以rt为根节点的子树的真实方案数，不就是A(rt)吗？这样的话就没有必要分情况了，在最后加个判断即可。
代码如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define rep(i,n) for (int i = 0; i < (n); ++i) 5 #define For(i,s,t) for (int i = (s); i <= (t); ++i) 6 #define rFor(i,t,s) for (int i = (t); i >= (s); --i) 7 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i) 8 #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) 9 10 #define pr(x) cout << #x << " = " << x << " " 11 #define prln(x) cout << #x << " = " << x << endl 12 13 #define LOWBIT(x) ((x)&(-x)) 14 15 #define ALL(x) x.begin(),x.end() 16 #define INS(x) inserter(x,x.begin()) 17 18 #define ms0(a) memset(a,0,sizeof(a)) 19 #define msI(a) memset(a,inf,sizeof(a)) 20 #define msM(a) memset(a,-1,sizeof(a)) 21 22 #define pii pair<int,int> 23 #define piii pair<pair<int,int>,int> 24 #define mp make_pair 25 #define pb push_back 26 #define fi first 27 #define se second 28 29 inline int gc(){ 30 static const int BUF = 1e7; 31 static char buf[BUF], *bg = buf + BUF, *ed = bg; 32 33 if(bg == ed) fread(bg = buf, 1, BUF, stdin); 34 return *bg++; 35 } 36 37 inline int ri(){ 38 int x = 0, f = 1, c = gc(); 39 for(; c<48||c>57; f = c==‘-‘?-1:f, c=gc()); 40 for(; c>47&&c<58; x = x*10 + c - 48, c=gc()); 41 return x*f; 42 } 43 44 typedef long long LL; 45 typedef unsigned long long uLL; 46 const int inf = 1e9 + 9; 47 const LL mod = 1e9 + 7; 48 const int maxN = 1e5 + 7; 49 50 struct Node{ 51 vector< int > next; 52 }; 53 54 int n, ans; 55 56 /* 57 设A(x) = 在以顶点x为根的子树中，所有满足使x所在子图不含黑色顶点，其余子图只含有1个黑色顶点的分割方案种数 58 设B(x) = 在以顶点x为根的子树中，所有满足每个子图只含有1个黑色顶点的分割方案种数 59 设C(x) = 在以顶点x为根的子树中，所有满足使x所在子图只含有1个黑色顶点，其余子图只含有1个黑色顶点的分割方案种数 60 则有： 61 dp[v][0] = A(v) + B(v) 62 dp[v][1] = B(v) 63 C(v) = B(v) 64 The answer is dp[0][1]. 65 */ 66 LL dp[maxN][2]; 67 Node nodes[maxN]; 68 int color[maxN]; 69 70 void dfs(int x) { 71 // 默认顶点x为白色 72 dp[x][0] = 1; 73 dp[x][1] = 0; 74 75 foreach(i, nodes[x].next) { 76 dfs(*i); 77 // dp[*i][0] 包含 A(*i) 和 C(*i)，对于A(*i)，令其与C(x)相连 78 // 而对于C(*i)，令其与C(x)分断 79 dp[x][1] = (dp[x][1] * dp[*i][0]) % mod; 80 // dp[x][0] 包含 A(x)，令其与C(*i)相连 81 dp[x][1] = (dp[x][1] + dp[x][0] * dp[*i][1]) % mod; 82 // 此时dp[x][0] = A(x) 83 // dp[x][0] * dp[*i][0] = A(x)*A(*i) + A(x)*C(*i) 84 // 依次是连接新子树的A(*i)部分和断掉新子树的C(*i)部分，两这都可以保证dp[x][0]更新后还是A(x) 85 dp[x][0] = (dp[x][0] * dp[*i][0]) % mod; 86 } 87 88 if(color[x] == 1) dp[x][1] = dp[x][0]; // 当根节点为黑色时，A(x)实际上是C(x)，而真正的A(x) = 0 89 else dp[x][0] = (dp[x][0] + dp[x][1]) % mod; // 此时 dp[x][0] = A(x) + C(x) 90 } 91 92 int main(){ 93 while(cin >> n) { 94 rep(i, n) nodes[i].next.clear(); 95 For(i, 1, n-1) { 96 int t; 97 cin >> t; 98 // 根据题目要求，并不需要加反向边 99 nodes[t].next.push_back(i); 100 } 101 rep(i, n) cin >> color[i]; 102 103 dfs(0); 104 105 cout << dp[0][1] <<endl; 106 } 107 return 0; 108 }