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

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

#### 样例解释 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](https://contests.ioi-jp.org/open-2020/index.html) T3 「[発電所](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2020/power/2020-open-power-statement.pdf) / [Power Plant](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2020/power/2020-open-power-statement-en.pdf)」