← 返回题目列表

AtCoder · agc008_f

F. 黑色半径

中文机器翻译题面 查看原题

分数: 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

可能有以下四种顶点颜色组合:

334d566ec1f4f38d23cd580044f1cd07.png

示例输入 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