Appleman and Tree

题面翻译

题目描述

给你一棵有 $n$ 个节点的树，下标从 $0$ 开始。

第 $i$ 个节点可以为白色或黑色。

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

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

输入格式

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

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

接下来一行 $n$ 个整数 $(x_0,x_1,\cdots,x_{n-1},0\leq x_i\leq 1)$，若 $x_i$ 为 $1$，则节点 $i$ 为黑色，否则为白色。

输出格式

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

题目描述

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$ ( $10^{9}+7$ ).

输入格式

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

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

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

输出格式

Output a single integer — the number of ways to split the tree modulo $1000000007$ ( $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