[COCI2020-2021#2] Svjetlo

有一个呈树状结构的吊灯，由 $n$ 个灯泡组成，这些灯泡之间有 $n-1$ 根电线连接。每个灯泡有一个按钮，能使灯泡的状态发生改变，即把打开的灯泡关闭，关闭的灯泡打开。你需要把所有的灯泡打开。 你可以选择一个序列，序列中两两相邻位置的灯泡相邻，灯泡可以在序列中出现多次。你可以依次改变序列中的灯泡的状态。 你需要计算出最短的符合题目要求的灯泡序列。保证至少有一个灯泡在开始时处于关闭状态。

第一行一个整数 $n$，表示灯泡的数量。 第二行一个长为 $n$ 的 01 序列，表示灯泡的状态，其中“0”代表关闭，“1”代表打开。 接下来 $n - 1$ 行每行两个整数 $x, y$，表示 $x$ 与 $y$ 之间有边。

输出序列的最小长度。可以证明这样的序列一定存在。

3
010
1 2
2 3

4

5
00000
1 2
2 3
2 4
3 5

7

5
00100
1 2
2 3
2 4
3 5

8

**【样例解释 #1】** 序列可以为 $1, 2, 3, 2$。 **【数据范围】** 对于 $100\%$ 的数据，$2 \leq n \leq 500,000$。 Subtask #1（$19$ pts）：$n \leq 100$。 Subtask #2（$27$ pts）：每个灯泡最多与两个灯泡相连。 Subtask #3（$27$ pts）：一开始所有灯泡均处于关闭状态。 Subtask #4（$27$ pts）：无附加限制。 #### 说明 译自 [Croatian Open Competition in Informatics 2020 ~ 2021 Round 2 E Svjetlo](https://hsin.hr/coci/contest2_tasks.pdf)。