给定一棵有 $N$ 个顶点的有根树，顶点编号为 $1$ 到 $N$，其中顶点 $1$ 为根。第 $i$ 条边 ($1 \le i \le N - 1$) 连接顶点 $U_i$ 和 $V_i$。

树的每个顶点都被涂成白色或黑色。顶点 $i$ ($1 \le i \le N$) 若 $A_i = 0$ 则为白色，若 $A_i = 1$ 则为黑色。

你可以执行任意次数（包括零次）以下操作：

• 选择一个叶子顶点 $x$，翻转从根到顶点 $x$ 的路径上所有顶点的颜色（将白色变为黑色，黑色变为白色，包括根和顶点 $x$）。

你的目标是最大化黑色顶点的数量。请问可以达到的最大黑色顶点数量是多少？

输入格式

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

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

• 输入中的所有值均为整数。
• $2 \le N \le 10^5$
• $0 \le A_i \le 1$ ($1 \le i \le N$)
• $1 \le U_i, V_i \le N$ ($1 \le i \le N - 1$)
• 给定的图是一棵树。

输出格式

输出通过执行任意次数操作所能达到的最大黑色顶点数量。

样例

输入格式 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