Codeforces 461 B. Appleman and Tree

2022-10-07 21:12:21

树形DP。。。

Appleman has a tree with n vertices. Some of the vertices (at least one) are colored black and other vertices are colored white.

Consider a set consisting of k (0?≤?k?<?n) edges of Appleman‘s tree. If Appleman deletes these edges from the tree, then it will split into (k?+?1) parts. Note, that each part will be a tree with colored vertices.

Now Appleman wonders, what is the number of sets splitting the tree in such a way that each resulting part will have exactly one black vertex? Find this number modulo 1000000007 (109?+?7).

Input

The first line contains an integer n (2??≤?n?≤?105) — the number of tree vertices.

The second line contains the description of the tree: n?-?1 integers p0,?p1,?...,?pn?-?2 (0?≤?pi?≤?i). Where pi means that there is an edge connecting vertex (i?+?1) of the tree and vertex pi. Consider tree vertices are numbered from 0 to n?-?1.

The third line contains the description of the colors of the vertices: n integers x0,?x1,?...,?xn?-?1 (xi is either 0 or 1). If xi is equal to1, vertex i is colored black. Otherwise, vertex i is colored white.

Output

Output a single integer — the number of ways to split the tree modulo 1000000007 (109?+?7).

Sample test(s)

input
3
0 0
0 1 1

output
2

input
6
0 1 1 0 4
1 1 0 0 1 0

output
1

input
10
0 1 2 1 4 4 4 0 8
0 0 0 1 0 1 1 0 0 1

output
27

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=100010;
const long long int mod=1000000007LL;

int n;
struct Edge
{
	int to,next;
}edge[3*maxn];

int Adj[maxn],Size;

void init()
{
	Size=0;
	memset(Adj,-1,sizeof(Adj));
}

void Add_Edge(int u,int v)
{
	edge[Size].to=v;
	edge[Size].next=Adj[u];
	Adj[u]=Size++;
}

int c[maxn];
long long int dp[maxn][2];

void dfs(int u,int fa)
{
	dp[u][c[u]]=1;
	for(int i=Adj[u];~i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v==fa) continue;
		dfs(v,u);
		dp[u][1]=(dp[u][1]*dp[v][1]%mod+dp[u][0]*dp[v][1]%mod+dp[u][1]*dp[v][0]%mod)%mod;
		dp[u][0]=(dp[u][0]*dp[v][0]%mod+dp[u][0]*dp[v][1]%mod)%mod;
	}
}

int main()
{
	init();
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int v;
		scanf("%d",&v);
		Add_Edge(i,v);
		Add_Edge(v,i);
	}
	for(int i=0;i<n;i++)
		scanf("%d",c+i);
	dfs(0,0);
	printf("%I64d\n",dp[0][1]);
	return 0;
}

Codeforces 461 B. Appleman and Tree

码农公寓

相关文章