You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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$ 中的每个字符都是 $\mathtt{0}$ 或 $\mathtt{1}$ 中的一种。第 $i\ (1\le i\le n)$ 个字符描述的是基站 $i$ 中的发电机组。如果是 $\mathtt{0}$，则表示第 $i$ 个基站中没有发电机组，如果是 $\mathtt{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

在样例输入中，基站 1,2,5,6 中有发电机组。

如果将基站 1,2,5 中的发电机组调至「打开」状态，在基站 1,2,5 中的发电机组将被激活，将会获得 3 日元。因为不需要支付修理费，所以利润就是 3 日元。因为这是你的利润的最大值，所以输出 3。

另一方面，如果将基站 1,5,6 中的发电机组调至「打开」状态，基站 2 中的发电机组将会损坏，基站 1,5,6 中的发电机组将被激活，你会获得 3 日元，并支付 1 日元的修理费，所以利润是 2 日元。

如果将基站 1,2,5,6 中的发电机组调至「打开」状态，基站 2 中的发电机组将会损坏，基站 1,5,6 中的发电机组将被激活，你会获得 3 日元，并支付 1 日元的修理费，所以利润是 2 日元。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（6 pts）：$n\le 16$；
• Subtask 2（41 pts）：$n\le 2000$；
• Subtask 3（53 pts）：无特殊限制。

对于全部数据，$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$ 是一个只包含 $\mathtt{0}$ 和 $\mathtt{1}$ 且长度为 $n$ 的字符串；
• $S$ 中至少包含一个 $\mathtt{1}$。

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