← 返回题目列表

AtCoder · ttpc2022_d

D. 异或树路径

中文机器翻译题面 查看原题

配点 : 200 点

問題文

在顶部 编号为 1, 2, \dots, N 编号的顶点 1 植根于 N 我有一棵有根的顶点树。 这是连接i 条边 (1 ≤ i ≤ N - 1) 是顶点 U_i 与边缘 V_i 。

树的每个顶点被涂成白色或黑色,顶点 i (1 ≤ i ≤ N) 是 A_i = 0 时为白色,A_i = 1 时为黑色。

想把树涂黑的黑木先生,可以进行以下操作任意次数,至少 0 次,黒最大化被涂颜色的顶点数量。选择

  • 葉个顶点,从根开始 x 该值应乘以 1 选择,并从根部 x 将路径上的顶点(包括两端)颜色反转(如果是白色则涂成黑色,如果是黑色则涂成白色)。

黑木先生可以得到多少个被涂成黑色的顶点的树?

制約

  • 所有输入均为整数
  • 2 \leq N \leq 10^5
  • 0 \leq A_i \leq 1 (1 ≤ i ≤ N)
  • 1 \leq U_i, V_i \leq N (1 ≤ i ≤ N - 1)
  • 给定的图是树

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \cdots A_N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

出力

执行问题文本中的操作。 如果你这样做 0 输出在执行任意次数操作后的黑色顶点数量的最大值。


入力例 1

5
1 0 0 1 0
1 2
1 3
3 4
3 5

出力例 1

5

按如下操作可以将所有顶点涂成黑色。

  1. 頂点 2 选择。 这会使顶点 1 变成白色,顶点 2 变成黑色。
  2. 頂点 5 选择。 这会使顶点 1 变成黑色,顶点 3 变成黑色,顶点 5 变成黑色。

入力例 2

6
1 1 0 0 1 0
3 1
2 5
1 2
4 1
2 6

出力例 2

5

入力例 3

9
1 0 1 0 1 0 1 0 1
2 9
1 2
6 9
3 8
4 5
5 9
2 8
7 8

出力例 3

6