Problem Description

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.

Input Format

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 Format

Output one integer, the minimum number of operations.

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

3

7
0 0 1 0 0 1 1
6 4
3 4
3 5
1 5
7 3
2 7

3

Hint

Constraints

For all testdata, it is guaranteed that $1 \le n \le 2\times 10^5$, and $0\le \mathrm{color}_i\le 1$.

Translated by ChatGPT 5