P11018 Monochrome Tree

You are given a tree rooted at node $1$. Each node $u$ can only have one of two colors: black or white. The initial color of each node $u$ is known and is denoted as $\mathrm{color}_u$. You have two operations: - Operation $1$: Flip the colors of all nodes on the path from any node $u$ to the root (the path includes $u$ and the root). - Operation $2$: Flip the colors of all nodes in the subtree rooted at any node $u$ (the subtree of $u$ includes $u$). You are asked: what is the minimum number of operations needed to make the entire tree black.

The first line contains an integer $n$, the number of nodes. The second line contains $n$ integers $\mathrm{color}_i$. $\mathrm{color}_i=0$ means node $i$ is initially white, and $\mathrm{color}_i=1$ means node $i$ is initially black. The next $n-1$ lines each contain two integers describing an edge connecting the two nodes.

Output one integer, the minimum number of operations.

#### Constraints For all testdata, it is guaranteed that $1 \le n \le 2\times 10^5$, and $0\le \mathrm{color}_i\le 1$. |$\text{Subtask}$|$n\leq$|Score|Special Properties| |:-:|:-:|:-:|:-:| |$0$|$5$|$3$|None| |$1$|$10$|$7$|None| |$2$|$2\times 10^3$|$29$|None| |$3$|$2\times 10^5$|$61$|None| Translated by ChatGPT 5