You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有 $n$ 个寄存器，编号为 $1 \sim n$。这些寄存器由 $n-1$ 条带有开关的电线连接。为了保证交换信息的顺利，保证每两个寄存器都可以通过若干条电线连接。

初始时每个寄存器存储的信息都是 $0$。小 H 每次可以独立地操纵所有电线的开关然后选择一个寄存器通电。若一个寄存器与一个通电的寄存器有开启的电线相连，则这个寄存器也会通电。所有通电的寄存器都会反转存储的信息（$0$ 会变成 $1$，$1$ 会变成 $0$）。小 H 想让寄存器存储他想要的信息，他希望你告诉他最少需要进行多少次通电。

输入格式

第一行，一个正整数 $n$，表示寄存器个数。

第二行，$n$ 个非负整数 $a_1, \ldots, a_n$，表示小 H 希望寄存器 $i$ 存储 $a_i$。保证 $a_i$ 为 $0$ 或 $1$。

接下来 $n - 1$ 行，每行两个正整数 $u, v$，表示寄存器 $u$ 和 $v$ 之间有一根电线。保证每两个寄存器都可以通过若干条电线连接。

输出格式

仅一行，一个非负整数，表示最少进行多少次通电。

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

2

15
1 0 0 0 0 1 0 1 1 1 0 0 1 1 0
10 2
1 7
1 5
9 7
14 2
4 11
6 5
9 15
4 5
5 3
5 14
13 5
5 8
5 12

4

提示

【样例解释 #1】

先将电线 $(1, 2)$ 关闭，其余开启，给寄存器 $1$ 通电，此时 $1$ 的信息翻转，所有寄存器存储的信息变为 1 0 0 0 0。

然后将电线 $(2, 4)$ 关闭，其余开启，给寄存器 $4$ 通电，此时 $4$ 的信息翻转，所有寄存器存储的信息变为 1 0 0 1 0，满足要求。

可以证明不存在更优的方案。

【数据范围】

本题采用捆绑测试。

• 子任务 1（20 分）：$n\le 5$。
• 子任务 2（20 分）：对于第 $i$ 根电线，$u=i$，$v=i+1$。
• 子任务 3（30 分）：不存在一对相邻的寄存器希望储存的信息相同。
• 子任务 4（30 分）：无特殊性质。

对于全部的数据，$1\le n\le 10^6$，$1\le u,v\le n$，$0 \le a_i \le 1$，每两个寄存器都可以通过若干条电线连接。