C. Combat on Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a rooted tree with $$$n$$$ vertices rooted at vertex $$$1$$$. Each vertex holds a binary value $$$v_i$$$ ($$$0$$$ or $$$1$$$). In one move, you choose a vertex $$$v$$$ and flip the value of every vertex on the path from $$$v$$$ to the root (inclusive). Find the minimum number of moves to make all vertices equal to $$$1$$$.

Input

The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$), denoting the number of nodes in the tree.

The next line contains $$$n$$$ integers $$$v_i$$$ ($$$v_i \in \{0, 1\}$$$), with the $$$i$$$-th integer denoting the value of node $$$i$$$.

The next $$$n-1$$$ lines contain $$$2$$$ integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$), denoting an edge connecting $$$a_i$$$ and $$$b_i$$$ in the tree.

—

Tests in subtasks are numbered from $$$1−25$$$ with samples skipped. Each test is worth $$$\frac{100}{25}=4$$$ points.

Tests $$$1-3$$$ satisfy $$$n \leq 20$$$.

Tests $$$4-10$$$ satisfy that the tree is a path. That is, there is an edge from node $$$i$$$ to node $$$i+1$$$ for all $$$1\le i\le n-1$$$.

Tests $$$11-25$$$ satisfy no additional constraints.

Output

Output one integer, the minimum number of moves to end with all vertices equal to $$$1$$$.

Example
Input
4
1 0 0 1
1 2
1 3
2 4
Output
2
Note

—

Problem Idea: jay_jayjay

Problem Preparation: theyashb

Occurrences: Novice C