#P461B. Appleman and Tree
Appleman and Tree
Appleman and Tree
题面翻译
题目描述
给你一棵有 个节点的树,下标从 开始。
第 个节点可以为白色或黑色。
现在你可以从中删去若干条边,使得剩下的每个部分恰有一个黑色节点。
问有多少种符合条件的删边方法,答案对 取模。
输入格式
第一行一个整数 ,表示节点个数。
接下来一行 个整数 ,表示树中有一条连接节点 和节点 的边。
接下来一行 个整数 ,若 为 ,则节点 为黑色,否则为白色。
输出格式
第一行一个整数,表示符合条件的删边方法的方案数对 取模后的值。
题目描述
Appleman has a tree with vertices. Some of the vertices (at least one) are colored black and other vertices are colored white.
Consider a set consisting of edges of Appleman's tree. If Appleman deletes these edges from the tree, then it will split into 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 ( ).
输入格式
The first line contains an integer ( ) — the number of tree vertices.
The second line contains the description of the tree: integers ( ). Where means that there is an edge connecting vertex of the tree and vertex . Consider tree vertices are numbered from to .
The third line contains the description of the colors of the vertices: integers ( is either or ). If is equal to , vertex is colored black. Otherwise, vertex is colored white.
输出格式
Output a single integer — the number of ways to split the tree modulo ( ).
样例 #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