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$$$表示按位异或运算。