LuoTianyi and XOR-Tree
Contest: Codeforces Round 872 (Div. 1)
Difficulty rating: 2500
Tags: data structures, dfs and similar, dp, dsu, greedy, trees

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.

$$$^{\dagger}$$$A 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 \le n \le 10^5$$$) — the number of vertices in the tree.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 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 \le u_i,v_i \le n, u_i \neq v_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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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 $$$3 \oplus 3=0$$$.

The bitwise XOR from the root to the leaf $$$5$$$ will be $$$4 \oplus 7 \oplus 3=0$$$.

The bitwise XOR from the root to the leaf $$$6$$$ will be $$$6 \oplus 5 \oplus 3=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 $$$20 \oplus 19 \oplus 7=0$$$.

The bitwise XOR from the root to the leaf $$$8$$$ will be $$$11 \oplus 27 \oplus 4 \oplus 19 \oplus 7=0$$$.

The bitwise XOR from the root to the leaf $$$4$$$ will be $$$16 \oplus 4 \oplus 19 \oplus 7=0$$$.

The bitwise XOR from the root to the leaf $$$7$$$ will be $$$16 \oplus 4 \oplus 19 \oplus 7=0$$$.

In the third example, the only leaf is the vertex $$$4$$$ and the bitwise XOR on the path to it is $$$1 \oplus 2 \oplus 1 \oplus 2 = 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.

Example input:
6
3 5 7 5 8 4
1 2
1 3
1 4
3 5
4 6

Example output:
3

Example input:
8
7 10 7 16 19 9 16 11
1 5
4 2
6 5
5 2
7 2
2 3
3 8

Example output:
3

Editorial:
You can first use dp[x][val] as the minimum times you need to change in the subtree x and all the value are val.
You can find that |dp[x][val1]-dp[x][val2]|<=1.So you can record the smaller dp[x][val]s and the vals.
And the merge can be finished with dsu on tree.
If there are val appears multi times, at least half of the values will be deleted, or just use the value from merge is ok.
So we proved that it's O(nlog^2n)