AT_ttpc2022_d.XOR Tree Path

有一棵以顶点 $1$ 为根、共 $N$ 个顶点的有根树，顶点编号为 $1, 2, \dots, N$。对于第 $i$ 条边（$1 \leq i \leq N-1$），它连接着顶点 $U_i$ 和顶点 $V_i$。

树上的每个顶点都被涂成了白色或黑色。对于顶点 $i$（$1 \leq i \leq N$），若 $A_i=0$，则该顶点为白色；若 $A_i=1$，则该顶点为黑色。

现在，「黑木」希望让树上被涂成黑色的顶点数量最大。为此，他可以进行任意次数（包括零次）如下操作：

• 任选一个叶子结点$x$，将从根到 $x$ 的路径上（包括两端）的所有顶点的颜色反转（即白色变成黑色，黑色变成白色）。

请问，通过若干次上述操作，最多能使多少个顶点变为黑色？

输入通过标准输入给出，格式如下：

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

输出能够通过若干次题目给定的操作后，顶点中被涂成黑色的最大数量。

样例解释 1

如样例所示，可以通过如下操作将所有顶点都涂黑：

1. 选择顶点 $2$，此时顶点 $1$ 变为白色，顶点 $2$ 变为黑色。
2. 选择顶点 $5$，此时顶点 $1$ 变为黑色，顶点 $3$ 变为黑色，顶点 $5$ 变为黑色。

数据范围

• 所有输入均为整数
• $2 \leq N \leq 10^5$
• $0 \leq A_i \leq 1$（$1 \leq i \leq N$）
• $1 \leq U_i, V_i \leq N$（$1 \leq i \leq N-1$）
• 所给图保证是一棵树

由 ChatGPT 5 翻译