配点 : 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
按如下操作可以将所有顶点涂成黑色。
- 頂点 2 选择。 这会使顶点 1 变成白色,顶点 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