Description

There is a tree-shaped chandelier consisting of $n$ light bulbs, connected by $n - 1$ wires. Each bulb has a button that toggles the bulb’s state: it turns an on bulb off, and an off bulb on. You need to turn all bulbs on.

You may choose a sequence in which every pair of adjacent bulbs in the sequence are adjacent in the tree, and a bulb may appear multiple times in the sequence. You then toggle the bulbs in the sequence in order.

You need to compute the shortest bulb sequence that satisfies the requirements. It is guaranteed that at least one bulb is initially off.

Input Format

The first line contains an integer $n$, the number of bulbs.
The second line contains a $01$ string of length $n$, describing the states of the bulbs, where “0” means off and “1” means on.
The next $n - 1$ lines each contain two integers $x, 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.

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

Hint

Sample Explanation #1

A valid sequence can be $1, 2, 3, 2$.

Constraints

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

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

Note

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

Translated by ChatGPT 5