Problem Description

There is a chandelier structured as a tree, consisting of $n$ light bulbs connected by $n-1$ wires. Each light bulb has a button that can change its state, i.e., turn an on bulb off and an off bulb on. You need to turn on all the light bulbs.

You can choose a sequence where each pair of adjacent positions in the sequence represents adjacent light bulbs, and a light bulb can appear multiple times in the sequence. You can change the state of the light bulbs in the sequence one by one.

You need to calculate the shortest sequence that meets the requirements of the problem. It is guaranteed that at least one light bulb is initially off.

Input Format

The first line contains an integer $n$, representing the number of light bulbs.
The second line contains a sequence of $n$ 0s and 1s, representing the state of the light bulbs, where "0" means off and "1" means on.
The next $n - 1$ lines each contain two integers $x$ and $y$, indicating that there is an edge between $x$ and $y$.

Output Format

Output the minimum length of the sequence. It can be proven that such a sequence always exists.

Sample Input and Output

Sample Input #1

3
010
1 2
2 3

Sample Output #1

4

Sample Input #2

5
00000
1 2
2 3
2 4
3 5

Sample Output #2

7

Sample Input #3

5
00100
1 2
2 3
2 4
3 5

Sample Output #3

8

Notes

[Sample Explanation #1]

The sequence can be $1, 2, 3, 2$.

[Data Range]

For $100\%$ of the data, $2 \leq n \leq 500,000$.

Subtask #1 ($19$ pts): $n \leq 100$.
Subtask #2 ($27$ pts): Each light bulb is connected to at most two other light bulbs.
Subtask #3 ($27$ pts): All light bulbs are initially off.
Subtask #4 ($27$ pts): No additional restrictions.

Notes

Translated from Croatian Open Competition in Informatics 2020 ~ 2021 Round 2 E Svjetlo.

见题面 Input 部分

见题面 Output 部分