#3363. 「JOI Open 2020」发电站

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

译自 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 则表示有发电机组。

输出格式

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

样例

样例输入 1

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

样例输出 1

3

样例说明 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 日元。

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

数据范围与提示

对于全部数据, 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

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

子任务编号 附加限制 分值
1 N\le 16 6
2 N\le 2\times 10^3 41
3 无附加限制 53