Background

Original link: https://oier.team/problems/X7D.

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

Problem Description

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.

Input Format

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 Format

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

5
1 0 0 1 0
1 2
2 3
2 4
3 5

2

15
1 0 0 0 0 1 0 1 1 1 0 0 1 1 0
10 2
1 7
1 5
9 7
14 2
4 11
6 5
9 15
4 5
5 3
5 14
13 5
5 8
5 12

4

Hint

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