#P461B. Appleman and Tree

Appleman and Tree

Appleman and Tree

题面翻译

题目描述

给你一棵有 nn 个节点的树,下标从 00 开始。

ii 个节点可以为白色或黑色。

现在你可以从中删去若干条边,使得剩下的每个部分恰有一个黑色节点。

问有多少种符合条件的删边方法,答案对 109+710^9+7 取模。

输入格式

第一行一个整数 n(1n105)n(1\leq n\leq 10^5),表示节点个数。

接下来一行 n1n-1 个整数 (p0,p1,,pn2,0pii)(p_0,p_1,\cdots,p_{n-2},0\leq p_i\leq i),表示树中有一条连接节点 pip_i 和节点 i+1i+1 的边。

接下来一行 nn 个整数 (x0,x1,,xn1,0xi1)(x_0,x_1,\cdots,x_{n-1},0\leq x_i\leq 1),若 xix_i11,则节点 ii 为黑色,否则为白色。

输出格式

第一行一个整数,表示符合条件的删边方法的方案数对 109+710^9+7 取模后的值。

题目描述

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

Consider a set consisting of k k (0<=k<n) (0<=k<n) edges of Appleman's tree. If Appleman deletes these edges from the tree, then it will split into (k+1) (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 1000000007 ( 109+7 10^{9}+7 ).

输入格式

The first line contains an integer n n ( 2<=n<=105 2<=n<=10^{5} ) — the number of tree vertices.

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

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

输出格式

Output a single integer — the number of ways to split the tree modulo 1000000007 1000000007 ( 109+7 10^{9}+7 ).

样例 #1

样例输入 #1

3
0 0
0 1 1

样例输出 #1

2

样例 #2

样例输入 #2

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

样例输出 #2

1

样例 #3

样例输入 #3

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

样例输出 #3

27