P11562 【MX-X7-T3】[LSOT-3] 寄存器

原题链接：。 这里不是 APIO，所以这个题也不是让你手搓 CPU。

有 $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$ 之间有一根电线。保证每两个寄存器都可以通过若干条电线连接。

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

**【样例解释 #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$，每两个寄存器都可以通过若干条电线连接。