← 返回题目列表

Codeforces · 1824/C

C. 洛天一和异或树

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

LuoTianyi 给你一棵树,其顶点都有值,树的根是顶点 $$$1$$$。

在一次操作中,您可以将一个顶点中的值更改为任何非负整数。

现在您需要找到使从根到叶子$$$^{\dagger}$$$ 的按位异或值为零所需执行的最少操作数。

$$$^{\dagger}$$$有根树中的叶子是只有一个邻居的顶点,而不是根。

输入

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

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$),第 $$$i$$$ 个数字表示第 $$$i$$$ 个顶点中的值。

接下来的 $$$n−1$$$ 行描述了树的边缘。第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i,v_i \le n, u_i \neq v_i$$$) — 由树的边连接的顶点。保证给定的边形成一棵树。

输出

打印单个整数 — 最小操作数。

示例

输入 #1

6
3 5 7 5 8 4
1 2
1 3
1 4
3 5
4 6

输出 #1

3

输入 #2

8
7 10 7 16 19 9 16 11
1 5
4 2
6 5
5 2
7 2
2 3
3 8

输出 #2

3

输入 #3

4
1 2 1 2
1 2
2 3
4 3

输出 #3

0

输入#4

9
4 3 6 1 5 5 5 2 7
1 2
2 3
4 1
4 5
4 6
4 7
8 1
8 9

输出#4

2

注意

第一个示例中的树:

如果我们将顶点 $$$2$$$ 中的值更改为 $$$3$$$,将顶点 $$$5$$$ 中的值更改为 $$$4$$$,将顶点 $$$6$$$ 中的值更改为 $$$6$$$,那么这棵树就可以了。

从根到叶子 $$$2$$$ 的按位异或将是 $$$3 \oplus 3=0$$$。

从根到叶子 $$$5$$$ 的按位异或将是 $$$4 \oplus 7 \oplus 3=0$$$。

从根到叶子 $$$6$$$ 的按位异或将是 $$$6 \oplus 5 \oplus 3=0$$$。

第二个示例中的树:

如果我们将顶点 $$$2$$$ 中的值更改为 $$$4$$$,将顶点 $$$3$$$ 中的值更改为 $$$27$$$,将顶点 $$$6$$$ 中的值更改为 $$$20$$$,那么这棵树就可以了。

从根到叶子 $$$6$$$ 的按位异或将是 $$$20 \oplus 19 \oplus 7=0$$$。

从根到叶子 $$$8$$$ 的按位异或将为 $$$11 \oplus 27 \oplus 4 \oplus 19 \oplus 7=0$$$。

从根到叶子 $$$4$$$ 的按位异或将是 $$$16 \oplus 4 \oplus 19 \oplus 7=0$$$。

从根到叶子 $$$7$$$ 的按位异或将是 $$$16 \oplus 4 \oplus 19 \oplus 7=0$$$。

在第三个示例中,唯一的叶子是顶点 $$$4$$$,其路径上的按位异或为 $$$1 \oplus 2 \oplus 1 \oplus 2 = 0$$$,因此我们不需要更改值。

在第四个示例中,我们可以将顶点 $$$1$$$ 中的值更改为 $$$5$$$,将顶点 $$$4$$$ 中的值更改为 $$$0$$$。

这里$$$\oplus$$$表示按位异或运算。