← Home 
write a go solution for Description:
LuoTianyi gives you a tree with values in its vertices, and the root of the tree is vertex 1.

In one operation, you can change the value in one vertex to any non-negative integer.

Now you need to find the minimum number of operations you need to perform to make each path from the root to leaf^dagger has a bitwise XOR value of zero.

^daggerA leaf in a rooted tree is a vertex that has exactly one neighbor and is not a root.

Input Format:
The first line contains a single integer n (2<=n<=10^5) — the number of vertices in the tree.

The second line contains n integers a_1,a_2,ldots,a_n (1<=a_i<=10^9), the i-th number represents the value in the i-th vertex.

Next n−1 lines describe the edges of the tree. The i-th line contains two integers u_i and v_i (1<=u_i,v_i<=n,u_ineqv_i) — the vertices connected by an edge of the tree. It's guaranteed that the given edges form a tree.

Output Format:
Print a single integer — the minimum number of operations.

Note:
The tree in the first example:

If we change the value in the vertex 2 to 3, the value in the vertex 5 to 4, and the value in the vertex 6 to 6, then the tree will be ok.

The bitwise XOR from the root to the leaf 2 will be 3oplus3=0.

The bitwise XOR from the root to the leaf 5 will be 4oplus7oplus3=0.

The bitwise XOR from the root to the leaf 6 will be 6oplus5oplus3=0.

The tree in the second example:

If we change the value in the vertex 2 to 4, the value in the vertex 3 to 27, and the value in the vertex 6 to 20, then the tree will be ok.

The bitwise XOR from the root to the leaf 6 will be 20oplus19oplus7=0.

The bitwise XOR from the root to the leaf 8 will be 11oplus27oplus4oplus19oplus7=0.

The bitwise XOR from the root to the leaf 4 will be 16oplus4oplus19oplus7=0.

The bitwise XOR from the root to the leaf 7 will be 16oplus4oplus19oplus7=0.

In the third example, the only leaf is the vertex 4 and the bitwise XOR on the path to it is 1oplus2oplus1oplus2=0, so we don't need to change values.

In the fourth example, we can change the value in the vertex 1 to 5, and the value in the vertex 4 to 0.

Here oplus denotes the bitwise XOR operation.. Output only the code with no comments, explanation, or additional text.