← 返回题目列表

Codeforces · 1709/E

E. 异或树

中文机器翻译题面 查看原题

给你一棵由 $$$n$$$ 个顶点组成的树。每个顶点上都写有一个数字;顶点 $$$i$$$ 上的数字等于 $$$a_i$$$。

回想一下,简单路径是最多访问每个顶点一次的路径。令路径的权重为其所包含的顶点上写入的值的按位异或。假设如果没有简单路径的权重 $$$0$$$,那么一棵树就是好树。

您可以多次应用以下操作(可能为零):选择树的一个顶点,并将其上写入的值替换为任意正整数。为了使树变得良好,您必须应用此操作的最少次数是多少?

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 顶点数。

第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i < 2^{30}$$$) - 写在顶点上的数字。

接下来是 $$$n - 1$$$ 行,每行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n; x \ne y$$$) 表示连接顶点 $$$x$$$ 和顶点 $$$y$$$ 的边。保证这些边形成一棵树。

输出

打印单个整数 - 为了使树良好而必须应用该操作的最少次数。

示例

输入 #1

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

输出 #1

2

输入 #2

4
2 1 1 1
1 2
1 3
1 4

输出 #2

0

输入 #3

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

输出 #3

2

注意

在第一个示例中,将顶点 $$$1$$$ 上的值替换为 $$$13$$$ 并将顶点 $$$4$$$ 上的值替换为 $$$42$$$ 就足够了。