P7163 [COCI 2020/2021 #2] Svjetlo

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.

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 the minimum length of the sequence. It can be proven that such a sequence always exists.

**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](https://hsin.hr/coci/archive/2020_2021/contest2_tasks.pdf)。 Translated by ChatGPT 5