CF1709E.XOR Tree

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?

给你一棵包含 $n$ 个顶点的树。每个顶点上写有一个数字；顶点 $i$ 上的数字为 $a_i$。

回顾一下，简单路径是指至多访问每个顶点一次的路径。定义该路径的权重为路径所经过的所有顶点上所写数值的按位异或（XOR）结果。若树中不存在权重为 $0$ 的简单路径，则称该树是“好的”。

你可以执行以下操作任意多次（也可以不执行）：选择树中的一个顶点，并将其上的数值替换为任意一个正整数。问：为使该树变为“好的”，最少需要执行多少次该操作？

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 \lt 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.

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 顶点的数量。

第二行包含 $n$ 个整数 $a_1$, $a_2$, ..., $a_n$（$1 \le a_i \lt 2^{30}$）—— 写在各顶点上的数字。

随后是 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$（$1 \le x, y \le n; x \ne y$），表示一条连接顶点 $x$ 与顶点 $y$ 的边。保证这些边构成一棵树。

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

输出一个整数——使树变为“好树”所需执行该操作的最少次数。

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

在第一个例子中，只需将顶点 $1$ 上的值替换为 $13$，并将顶点 $4$ 上的值替换为 $42$。