1500 苹果曼和树
苹果曼有一棵n个点的树。有一些（至少一个）结点被标记为黑色，有一些结点被标记为白色。
现在考虑一个包含k(0 ≤ k < n)条树边的集合。如果苹果曼删除这些边，那么会将这个树分成(k+1)个部分。每个部分还是一棵树。
现在苹果曼想知道有多少种边的集合，可以使得删除之后每一个部分恰好包含一个黑色结点。答案对1000000007 取余即可。
输入
单组测试数据。 第一行有一个整数n (2 ≤ n ≤ 10^5)，表示树中结点的数目。 第二行有n-1个整数p[0],p[1],...,p[n-2] (0 ≤ p[i] ≤ i)。表示p[i]和(i+1)之间有一条边。结点从0开始编号。 第三行给出每个结点的颜色，包含n个整数x[0],x[1],...,x[n-1] (x[i]是0或者1)。如果x[i]是1，那么第i个点就是黑色的，否则是白色的。
输出
输出答案占一行。
输入样例
3
0 0
0 1 1
输出样例
2
#include <bits/stdc++.h> #define rg register int using namespace std; typedef long long ll; const ll mod = 1e9 + 7; const int maxn = 2e5 + 10; struct node { int to, nx; } o[maxn]; int n, tot, head[maxn]; inline void add_edge(int u, int v) { o[++tot].to = v; o[tot].nx = head[u]; head[u] = tot; } int color[maxn]; ll dp[maxn][6]; inline void solve(int cur, int f) { dp[cur][color[cur]] = 1; for (register int i = head[cur]; i; i = o[i].nx) { int to = o[i].to; if (to == f)continue; solve(to, cur); dp[cur][1] = ((dp[cur][1] * (dp[to][1] + dp[to][0])) % mod + dp[cur][0] * dp[to][1] % mod) % mod; dp[cur][0] = (dp[cur][0] * (dp[to][0] + dp[to][1])) % mod; } } int main() { #ifndef ONLINE_JUDGE freopen("splay.txt", "r", stdin); #endif scanf("%d", &n); for (register int i = 1; i < n; ++i) { int x; scanf("%d", &x); add_edge(x, i); //add_edge(i,x); } for (register int i = 0; i < n; ++i)scanf("%d", &color[i]); solve(0, -1); printf("%lld\n", dp[0][1]); return 0; }