题目描述

译自 JOI Open 2020 T3 「発電所 / Power Plant」

JOI 发电站有 $N$ 个基站并从 $1$ 到 $N$ 编号。这些基站用 $N-1$ 条电线相连。第 $i\ (1\le i\le N-1)$ 条电线连接基站 $A_i$ 与基站 $B_i$，并且是双向连接的。通过电线我们可以从任意基站出发，到达任意基站。

JOI 发电站的每个基站至多有一个发电机组。每个发电机组都有一个开关。开始时，所有发电机组的开关都是「关闭」状态的。你是 JOI 发电站的负责人。你可以选择一些发电机组，并将这些选择的发电机组的开关调至「打开」状态（允许不选择任何发电机组）。发电机组有如下性质：

• 假设 $x,y,z$ 基站有发电机组。此外，假设我们可以按 $x$ 到 $y$ 到 $z$ 的顺序经过这三个基站，且不经过相同的电线两次。如果 $x$ 和 $z$ 基站的发电机组开关都是「打开」状态，那么 $y$ 基站的发电机组就会损坏。
• 如果开关处于「打开」状态并且发电机组未损坏，这个发电机组就会被激活。

最终，会根据激活的发电机组给你奖励。对于每个激活的发电机组，你会获得 $1$ 日元。然而，你也要花钱修理损坏的发电机组。对于每个损坏的发电机组，你需要支付 $1$ 日元。获得的奖励减去修理的花费的总额就是你的利润。

给出当前基站和电线的连接情况以及发电机组的信息，计算你能获得的最大利润。

输入格式

第一行一个整数 $N$，表示基站个数；

接下来 $N-1$ 行，每行两个整数 $A_i,B_i$；

接下来一行，一个长为 $N$ 的字符串 $S$，表示每个基站中是否有发电机组。$S$ 中的每个字符都是 $\texttt 0$ 或 $\texttt 1$ 中的一种。第 $i\ (1\le i\le N)$ 个字符描述的是基站 $i$ 中的发电机组。如果是 $\texttt 0$，则表示第 $i$ 个基站中没有发电机组，如果是 $\texttt 1$ 则表示有发电机组。

输出格式

输出一行，表示当你选择一些发电机组，并将所有选择的发电机组开关都调至「打开」状态时，你能获得的最大利润。

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

3

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

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

5

数据范围与提示

对于全部数据，$1\le N\le 2\times 10^5$，保证：

• $1\le A_i,B_i\le N\ (1\le i\le N-1)$；
• $A_i\neq B_i\ (1\le i\le N-1)$；
• 可以通过电线从任意基站出发到达任意基站；
• $S$ 是一个只包含 $\texttt 0$ 和 $\texttt 1$ 且长度为 $N$ 的字符串；
• $S$ 中至少包含一个 $\texttt 1$。

详细子任务附加限制与分值如下表：