XOR Tree
Contest: Educational Codeforces Round 132 (Rated for Div. 2)
Difficulty rating: 2400
Tags: bitmasks, data structures, dfs and similar, dsu, greedy, trees

You are given a tree consisting of $$$n$$$ vertices. A number is written on each vertex; the number on vertex $$$i$$$ is equal to $$$a_i$$$.

Recall that a simple path is a path that visits each vertex at most once. Let the weight of the path be the bitwise XOR of the values written on vertices it consists of. Let's say that a tree is good if no simple path has weight $$$0$$$.

You can apply the following operation any number of times (possibly, zero): select a vertex of the tree and replace the value written on it with an arbitrary positive integer. What is the minimum number of times you have to apply this operation in order to make the tree good?

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of vertices.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i < 2^{30}$$$) — the numbers written on vertices.

Then $$$n - 1$$$ lines follow, each containing two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n; x \ne y$$$) denoting an edge connecting vertex $$$x$$$ with vertex $$$y$$$. It is guaranteed that these edges form a tree.

Output format:
Print a single integer — the minimum number of times you have to apply the operation in order to make the tree good.

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

Note:
In the first example, it is enough to replace the value on the vertex $$$1$$$ with $$$13$$$, and the value on the vertex $$$4$$$ with $$$42$$$.

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

Example output:
2

Example input:
4
2 1 1 1
1 2
1 3
1 4

Example output:
0

Editorial:
To begin with, we note that there are no restrictions on the values that can be written on the vertices, so we can use numbers of the form $$$2^{30+x}$$$ for the $$$x$$$-th replacement. Then, if we replaced the value of a vertex, then no path passing through this vertex has weight $$$0$$$.
Let's root the tree at the vertex number $$$1$$$. We can use a greedy approach: consider some vertex $$$v$$$ such that it is the LCA for two vertices $$$x$$$ and $$$y$$$, the path between which has XOR equal to $$$0$$$. Among such vertices $$$v$$$, pick one with the maximum distance from the root. We need to change at least one vertex on the path $$$(x, y)$$$. It turns out that changing the vertex $$$v$$$ is always no worse than changing any other vertex $$$u$$$ on this path, because all the remaining bad paths that pass through the vertex $$$u$$$ also pass through the vertex $$$v$$$ (that's why we have chosen the deepest LCA). This means that in order to solve the problem, it is necessary to quickly find the deepest LCA of some bad path.
For the convenience of solving the problem, let's denote the XOR on the path $$$(x,y)$$$ as $$$b_x \oplus b_y \oplus a_{LCA(x,y)}$$$, where $$$b_v$$$ is XOR on the path from the root to the vertex $$$v$$$. For all vertices $$$v$$$, let's maintain a set of values $$$b_x$$$, such that $$$x$$$ belongs to the subtree of $$$v$$$. Let's use the small-to-large method to obtain such sets. Also, during the union of sets, we can check if there is a bad path in this subtree, i. e. if two values in the sets we merge have the same XOR as the value written on the current vertex (because that's when the XOR on path is $$$0$$$). If such a path exists, then we have to change the value of the vertex $$$v$$$ and mark that the vertices of this subtree cannot be the ends of a bad path anymore — that means we just clear the set instead of pulling it up the tree.
This solution works in $$$O(n \log^2 n)$$$.