JOI 发电厂有 $N$ 个基地，编号为 $1$ 到 $N$。这些基地由 $N-1$ 条电线连接。第 $i$ 条电线 ($1 \le i \le N-1$) 连接基地 $A_i$ 和基地 $B_i$，且是双向的。我们可以通过一些电线从任意一个基地到达另一个基地。

JOI 发电厂的每个基地最多有一个发电机。每个发电机都有一个开关。起初，所有发电机的开关都是关闭（OFF）的。你是 JOI 发电厂的厂长。你可以选择一些发电机，并将所选发电机的开关打开（ON）。（也可以选择不打开任何发电机。）发电机具有以下特性：

• 假设基地 $x, y, z$ 都有发电机。此外，假设我们可以按顺序从基地 $x$ 到达基地 $y$，再从基地 $y$ 到达基地 $z$，且过程中不经过同一条电线两次。如果基地 $x$ 和基地 $z$ 的发电机开关都处于开启（ON）状态，那么基地 $y$ 的发电机就会损坏。
• 如果发电机的开关处于开启（ON）状态且没有损坏，它就会被激活。

最后，你将从激活的发电机中获得奖励。每个激活的发电机你将获得 $1$ 日元。然而，你还必须支付损坏发电机的维修费用。每个损坏的发电机你必须支付 $1$ 日元。总奖励减去总维修费用即为你的利润。

编写一个程序，在给定基地和电线的排列方式以及发电机信息的情况下，计算你的最大利润。

输入格式

从标准输入读取以下数据：

$N$ $A_1$ $B_1$ $\vdots$ $A_{N-1}$ $B_{N-1}$ $S$

其中 $S$ 是一个长度为 $N$ 的字符串，表示各基地的发电机情况。$S$ 的每个字符要么是 $0$，要么是 $1$。第 $i$ 个字符 ($1 \le i \le N$) 描述了基地 $i$ 的发电机情况。如果基地 $i$ 没有发电机，则为 $0$；如果基地 $i$ 有发电机，则为 $1$。

输出格式

向标准输出打印一行。输出应包含当你选择一些发电机并将所选发电机的开关全部打开时，你所能获得的最大利润。

数据范围

• $1 \le N \le 200\,000$。
• $1 \le A_i \le N$ ($1 \le i \le N-1$)。
• $1 \le B_i \le N$ ($1 \le i \le N-1$)。
• $A_i \neq B_i$ ($1 \le i \le N-1$)。
• 我们可以通过一些电线从任意一个基地到达另一个基地。
• $S$ 是一个由 $0, 1$ 组成的长度为 $N$ 的字符串。
• $S$ 中至少包含一个 $1$。

子任务

1. (6 分) $N \le 16$。
2. (41 分) $N \le 2\,000$。
3. (53 分) 无附加限制。

样例

样例输入 1

6
2 3
4 3
1 3
3 5
6 2
110011

样例输出 1

3

样例输入 2

8
1 2
3 5
6 4
4 5
5 2
7 2
2 8
11111111

样例输出 2

3

样例输入 3

16
7 10
5 11
9 4
14 12
2 11
14 16
4 2
1 13
11 3
7 1
15 9
2 1
11 6
14 9
8 9
0111111001001110

样例输出 3

5