P11562 [MX-X7-T3] [LSOT-3] Registers

Original link: . This is not APIO, so this problem is not asking you to build a CPU by hand.

There are $n$ registers, numbered $1 \sim n$. These registers are connected by $n - 1$ wires with switches. To ensure smooth information exchange, it is guaranteed that every pair of registers can be connected through some wires. Initially, the information stored in every register is $0$. Each time, Xiao H can independently toggle the switches of all wires, and then choose one register to power on. If a register is connected to a powered register by an **enabled wire**, then this register will also be powered on. All powered registers will flip their stored information ($0$ becomes $1$, and $1$ becomes $0$). Xiao H wants the registers to store the information he wants, and he wants you to tell him the minimum number of **power-on operations** needed.

The first line contains a positive integer $n$, representing the number of registers. The second line contains $n$ non-negative integers $a_1, \ldots, a_n$, where $a_i$ means Xiao H wants register $i$ to store $a_i$. It is guaranteed that $a_i$ is either $0$ or $1$. The next $n - 1$ lines each contain two positive integers $u, v$, indicating that there is a wire between registers $u$ and $v$. It is guaranteed that every pair of registers can be connected through some wires.

Output a single line containing a non-negative integer, representing the minimum number of **power-on operations**.

**Sample Explanation #1** First, turn off wire $(1, 2)$ and turn on all the others, then power on register $1$. At this time, the information in $1$ is flipped, and the information stored in all registers becomes `1 0 0 0 0`. Then, turn off wire $(2, 4)$ and turn on all the others, then power on register $4$. At this time, the information in $4$ is flipped, and the information stored in all registers becomes `1 0 0 1 0`, which meets the requirement. It can be proven that there is no better solution. **Constraints** **This problem uses bundled testdata.** - Subtask 1 (20 points): $n \le 5$. - Subtask 2 (20 points): For the $i$-th wire, $u=i$, $v=i+1$. - Subtask 3 (30 points): There does not exist a pair of adjacent registers that want to store the same information. - Subtask 4 (30 points): No special properties. For all testdata: $1 \le n \le 10^6$, $1 \le u, v \le n$, $0 \le a_i \le 1$, and every pair of registers can be connected through some wires. Translated by ChatGPT 5