题目描述
繁华中学有一棵苹果树。苹果树有 n 个节点（也就是苹果），n − 1 条边（也就 是树枝）。调皮的 Evensgn 爬到苹果树上。他发现这棵苹果树上的苹果有两种：一 种是黑苹果，一种是红苹果。Evensgn 想要剪掉 k 条树枝，将整棵树分成 k + 1 个 部分。他想要保证每个部分里面有且仅有一个黑苹果。请问他一共有多少种剪树枝 的方案？
输入
第一行一个数字 n，表示苹果树的节点（苹果）个数。 第二行一共 n − 1 个数字 p0, p1, p2, p3, …, pn−2，pi 表示第 i + 1 个节点和 pi 节 点之间有一条边。注意，点的编号是 0 到 n − 1。 第三行一共 n 个数字 x0, x1, x2, x3, …, xn−1。如果 xi 是 1，表示 i 号节点是黑 苹果；如果 xi 是 0，表示 i 号节点是红苹果。
输出
输出一个数字，表示总方案数。答案对 109 + 7 取模。
样例输入
样例输入 1
3
0 0
0 1 1
样例输入 2
6
0 1 1 0 4
1 1 0 0 1 0
样例输入 3
10
0 1 2 1 4 4 4 0 8
0 0 0 1 0 1 1 0 0 1
样例输出
样例输出 1
2
样例输出 2
1
样例输出 3
27
提示
数据范围 对于 30% 的数据，1 ≤ n ≤ 10。 对于 60% 的数据，1 ≤ n ≤ 100。 对于 80% 的数据，1 ≤ n ≤ 1000。 对于 100% 的数据，1 ≤ n ≤ 105。 对于所有数据点，都有 0 ≤ pi ≤ n − 1，xi = 0 或 xi = 1。 特别地，60% 中、80% 中、100% 中各有一个点，树的形态是一条链。
题解
f[x][0]表示与其父边相连的连通块内没有黑苹果的方案数，
f[x][1]则表示有黑苹果，
如果父边被切断，相当于没有黑苹果
初始化时，假设切掉父边，f[x][0]=1,f[x][1]=0;
递归回时转移,每递归回一个子树,f[x][1]=f[x][1]*f[v][0]+f[x][0]*f[v][1],f[x][0]=f[x][0]*f[v][0];
最后处理完每个子树时,若其为黑苹果f[x][1]=f[x][0],否则f[x][0]=f[x][0]+f[x][1]（可以切掉）
Mycode
/**
******************************************************************************
* @file Evensgn
* @author WildRage
* @version v 1.0
* @date 2017-5-10 10:55:23
* @brief
******************************************************************************
*/
#include <cstdio>
#include <cstring>
#include <vector>
const int P = 1e9 + 7;
namespace Mine_WorkSpace
{
struct data
{
struct edge
{
int END, next;
} v[200005];
int first[100005], p;
data()
{
memset(first, -1, sizeof(first));
p = 0;
}
void add(int a, int b)
{
v[p].END = b;
v[p].next = first[a];
first[a] = p++;
}
} Edge;
bool color[100005];
long long f[100005][2];
void DP(int rt, int fa)
{
f[rt][0] = 1;
f[rt][1] = 0;
for (int i = Edge.first[rt]; i != -1; i = Edge.v[i].next)
{
if (fa != Edge.v[i].END)
{
DP(Edge.v[i].END, rt);
f[rt][1] = (f[rt][1] * f[Edge.v[i].END][0]) % P;
f[rt][1] = (f[rt][1] + f[Edge.v[i].END][1] * f[rt][0]) % P;
f[rt][0] = (f[rt][0] * f[Edge.v[i].END][0]) % P;
}
}
if (color[rt])
f[rt][1] = f[rt][0];
else
f[rt][0] = (f[rt][1] + f[rt][0]) % P;
}
int Main()
{
int n;
scanf("%d", &n);
int a, b;
for (int i = 1; i < n; i++)
{
scanf("%d", &b);
Edge.add(i + 1, b + 1), Edge.add(b + 1, i + 1);
}
for (int i = 1; i <= n; i++)
{
scanf("%d", &a);
if (a)
color[i] = 1;
}
DP(1,0);
printf("%lld\n", f[1][1]);
// Print_tree(1);
// while(1);
}
}
int main() { Mine_WorkSpace::Main(); }