XOR Tree

你有一棵无根树，点数为 $n$，每个点有个点权 $a_u$，定义一条路径 $P(u,v)$ 的权值为经过的**所有点的点权的异或和**。定义一棵树是合法的，当且仅当树上所有**简单路径**（只经过每个点一次的路径）的的权值都不为 $0$。 你可以对权值进行修改，可以改成**任意正整数**，问最少修改多少次才能让这棵树合法。 输出最小修改次数。 $n\leq 2\times 10^5,a_i\leq 2^{30}$

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?

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.

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

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

2

4
2 1 1 1
1 2
1 3
1 4

0

5
2 2 2 2 2
1 2
2 3
3 4
4 5

2

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 $ .