CF1709E XOR Tree

给定一棵包含 $n$ 个顶点的树。每个顶点上写有一个数字，第 $i$ 个顶点上的数字为 $a_i$。 我们称一条简单路径为每个顶点最多访问一次的路径。路径的权值定义为该路径上所有顶点的值的按位异或。我们称一棵树是“好”的，如果不存在权值为 $0$ 的简单路径。 你可以进行如下操作任意次（也可以不进行）：选择树上的一个顶点，将其上的值替换为任意正整数。请问，最少需要进行多少次操作，才能使这棵树变为“好”的？

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示顶点数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i < 2^{30}$），表示每个顶点上的数字。 接下来 $n-1$ 行，每行包含两个整数 $x$ 和 $y$（$1 \le x, y \le n; x \ne y$），表示一条连接顶点 $x$ 和顶点 $y$ 的边。保证这些边构成一棵树。

输出一个整数，表示最少需要进行多少次操作，才能使这棵树变为“好”的。

在第一个样例中，只需将顶点 $1$ 上的值替换为 $13$，将顶点 $4$ 上的值替换为 $42$ 即可。 由 ChatGPT 4.1 翻译