ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

8585: Birds in the tree

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：2 通过：1
提交提交记录统计Web Board

题目描述

One day, when NIO was walking under the tree, he found that there are birds standing on the tree, and each bird is standing on one leaf. He wondered about in how many sub-trees form by connected vertex-induced subgraphs from the original tree, all birds are in the same gender. The number would be very large, just mod 109+7 in the output.

输入格式

For each case, the first line contains an integer,  n, denoting the number of nodes on the tree. The second line is a binary string, where 1 denotes the male birds and 0 denotes the female birds.
Following by n−1 lines. In each line there are two integers, xi,yi, denoting there is a path connecting node x and node y.
1≤n≤3×105,1≤ xi,yi≤n

输出格式


Output a number module 109+7, the number of subgraphs of the given tree that form trees where all its leaves are the same gender of birds standing on.

输入样例 复制 

7
1011111
1 2
1 3
2 4
3 5
2 6
4 7

输出样例 复制 

28

分类标签