问题 A: Evensgn 剪树枝
时间限制: 1 Sec 内存限制: 128 MB
题目描述
繁华中学有一棵苹果树。苹果树有 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 取模。
样例输入
样例输入 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[i][0]为以i为根节点是如果有k个黑苹果，那就正好对其子树剪了k刀，f[i][1]为对其子树剪了k-1刀
因为我们发现如果总共有p个黑苹果，对于整颗树来说一定是剪了p-1根树枝的，那么状态转移一定是有上面俩个状态转移过来的。
所以我们对这个树先进行一遍dfs，预处理出其fa和size数组，size数组的含义是其子树中（包括他自己）含有多少个黑苹果。
那么对于节点i来说，我们要分两种情况进行考虑：：
①：这个苹果是个黑的，那么所有他的子节点如果为son，f[i][1]一定是有f[son][0]转移过来的，因为包含他自己就代表着他自己没有办法被砍，那这个状态只能是1
②：如果这个苹果是红色的，那就要比较麻烦一点了。。首先对于f[i][0]是其所有子节点f[son][0]+f[son][1],带便这这条枝被砍掉，那么f[son][1]就会变为f[son][0]，所以要求和。然后对所有的f[son][0]进行相乘（一个简单的分步乘法原理(⊙﹏⊙)b），这就是f[i][0],sum==f[i][0];
而f[i][1]就为(sum/f[son][0]*f[son][1])的和；因为只有一个是少砍一个的，其他的都是砍满的，方案数相乘。
所以最终的结果就是f[0][1]（我是从0开始定义的，而p个苹果必须留一个，所以是1）；
除法的时候因为有取模，所以要用逆元处理一下即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define mod 1000000007
int n,m,num,x,y;
int adj[],w[];
struct edge{
int s,t,next;
}k[];
int read(){
int sum=;char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<=''){sum=sum*+ch-'';ch=getchar();}
return sum;
}
void init(int s,int t){
k[num].s=s;k[num].t=t;
k[num].next=adj[s];adj[s]=num++;
k[num].s=t;k[num].t=s;
k[num].next=adj[t];adj[t]=num++;
}
int f[][];
int fa[],size[];
long long ks(long long p,int n){
long long sq=;
while(n){
if(n&) sq=sq*p%mod;
p=p*p%mod;
n>>=;
}
return sq;
}
void dfs(int x){
if(w[x]) size[x]=;
for(int i=adj[x];i!=-;i=k[i].next){
int o=k[i].t;
if(o!=fa[x]){
fa[o]=x;
dfs(o);
size[x]+=size[o];
}
}
}
void Dp(int x){
long long sum=;
if(!w[x]){
for(int i=adj[x];i!=-;i=k[i].next){
int o=k[i].t;
if(o==fa[x]||!size[o]) continue;
Dp(o);
f[o][]+=f[o][];f[o][]%=mod;
sum*=f[o][];sum%=mod;
}
f[x][]=sum;
for(int i=adj[x];i!=-;i=k[i].next){
int o=k[i].t;
if(o==fa[x]||!size[o]) continue;
int pl=sum*ks(f[o][],mod-)%mod*f[o][]%mod;
f[x][]+=pl;f[x][]%=mod;
}
}
else{
for(int i=adj[x];i!=-;i=k[i].next){
int o=k[i].t;
if(o==fa[x]||!size[o]) continue;
Dp(o); f[o][]+=f[o][];f[o][]%=mod;
sum*=f[o][];sum%=mod;
}
f[x][]=sum;
}
}
int main(){
//freopen("tree.in","r",stdin);
//freopen("tree.out","w",stdout);
memset(fa,-,sizeof(fa));
memset(adj,-,sizeof(adj));
n=read();
for(int i=;i<n;++i){
x=read();
init(x,i);
}
for(int i=;i<n;++i)
w[i]=read();
dfs();Dp();
printf("%d\n",f[][]);
return ;
}