题目描述

有一个呈树状结构的吊灯，由 $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。