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个点就是黑色的,否则是白色的。
输出
输出答案占一行。
输入样例
30 00 1 1
输出样例
2
#include#define rg register intusing 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;}