Evensgn 剪树枝 树规

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](可以切掉)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 100050
#define mod 1000000007ll
using namespace std;
int n,c[N],fa[N];
long long f[N][2];
int e=1,head[N];
struct edge{
	int u,v,next;
}ed[2*N];
void add(int u,int v){
	ed[e].u=u;ed[e].v=v;
	ed[e].next=head[u];head[u]=e++;
}
void dfs(int x){
	f[x][0]=1;f[x][1]=0;
	for(int i=head[x];i;i=ed[i].next){
		int v=ed[i].v;
		if(v==fa[x]) continue;
		fa[v]=x; dfs(v);
		f[x][1]=(f[x][1]*f[v][0])%mod;
		f[x][1]=(f[x][1]+(f[x][0]*f[v][1])%mod)%mod;
		f[x][0]=(f[x][0]*f[v][0])%mod;
	}
	if(c[x]) f[x][1]=f[x][0];
	else f[x][0]=(f[x][0]+f[x][1])%mod;
}
int main(){
	//freopen("tree.in","r",stdin);
	//freopen("tree.out","w",stdout);
	scanf("%d",&n);int a;
	for(int i=2;i<=n;i++){
		scanf("%d",&a);a++; 
		add(i,a); add(a,i);
	}
	for(int i=1;i<=n;i++)
		scanf("%d",&c[i]);
	dfs(1);
	printf("%lld
",f[1][1]);
	return 0;
}