分数: 1900 点
问题陈述
有一棵树 N 顶点。 顶点已编号 1 通过 N。 对于每个 1 ≤ i ≤ N - 1, i第一条边连接顶点 a_i 和 b_i。 所有边的长度为 1.
Snuke 喜欢一些顶点。
他最喜欢的顶点的信息以字符串形式提供给您 s 长度 N。
对于每个 1 ≤ i ≤ N, s_i is 1 如果 Snuke 喜欢顶点 i,和 0 如果他不喜欢顶点 i.
最初,所有顶点都是白色的。 Snuke 将执行以下操作一次:
- 选择一个顶点 他喜欢的 v ,以及一个非负整数 d。然后,将距离为 的所有顶点都涂成黑色 v 最多 d.
求运算后顶点可能的颜色组合数。
约束
- 2 ≤ N ≤ 2×10^5
- 1 ≤ a_i, b_i ≤ N
- 给定的图是一棵树。
- |s| = N
- s 包括
0和1. - s 至少包含一次
1.
部分分数
- 在测试集中值得 1300 点, s 仅包含
1.
输入
输入由标准输入按以下格式给出:
N
a_1 b_1
a_2 b_2
:
a_{N - 1} b_{N - 1}
s
输出
打印运算后顶点可能的颜色组合数。
示例输入 1
4 1 2 1 3 1 4 1100
示例输出 1
4
可能有以下四种顶点颜色组合:
示例输入 2
5 1 2 1 3 1 4 4 5 11111
示例输出 2
11
这种情况满足部分分数的附加约束。
示例输入 3
6 1 2 1 3 1 4 2 5 2 6 100011
示例输出 3
8