P10723 [GESP202406 Level 7] Black-White Flip.

Related multiple-choice and true/false questions: .

Xiao Yang has a tree with $n$ nodes. Each node in the tree is either white or black. Xiao Yang considers a tree to be a beautiful tree if and only if, after deleting all white nodes, the remaining nodes still form a tree. In each operation, Xiao Yang can choose one white node and change its color to black. He wants to know the minimum number of operations needed to make the tree become a beautiful tree.

The first line contains a positive integer $n$, representing the number of nodes in the tree. The second line contains $n$ non-negative integers $a_1,a_2,\ldots,a_n$. If $a_i=0$, then node $i$ is white; otherwise, it is black. Then follow $n-1$ lines. Each line contains two positive integers $x_i,y_i$, indicating that there is an edge connecting node $x_i$ and node $y_i$.

Output one integer, representing the minimum number of operations needed.

### Sample Explanation Changing nodes $1$ and $3$ to black is enough to make the tree a beautiful tree. At this time, after deleting the white node $5$, the remaining black nodes still form a tree. ### Constraints Subtask ID | Percentage of testdata | $n$ | $a_i$ | Special condition :-:|:-:|:-:|:-:|:-: $1$ | $30\%$ | $\leq 10^5$ | $0\leq a_i\leq 1$ | The tree is a chain. $2$ | $30\%$ | $\leq 10^5$ | $0\leq a_i\leq 1$ | Only two nodes are black. $3$ | $40\%$ | $\leq 10^5$ | $0\leq a_i\leq 1$ | None. For all testdata, it is guaranteed that $1\leq n\leq 10^5$ and $0\leq a_i\leq 1$. Translated by ChatGPT 5