题目描述

给定一棵包含 $n$ 个节点的树，每个节点有一个权值 $a_i$。定义一条路径的异或值为路径上所有节点权值的异或和。现在允许修改任意节点的权值为任意非负整数，求最少需要修改多少个节点才能使得这棵树中不存在任何异或和为0的简单路径。

输入格式

第一行包含一个整数 $n$，表示节点数。

第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ ($0 \leq a_i \leq 2^{30}$)，表示各节点的初始权值。

接下来 $n-1$ 行每行两个整数 $u, v$，表示树的一条边。

输出格式

输出一个整数，表示最少需要修改的节点数。

4
1 2 3 4
1 2
2 3
2 4

1

样例解释

将节点 $2$ 的权值修改为 $0$ 后，所有路径的异或和都不为 $0$ 。例如：

• 路径 $1-2$ 的异或和为 $1 \oplus 0=1$
• 路径 $2-3$ 的异或和为 $0\oplus3 =3$
• 路径 $1-2-3$ 的异或和为 $1\oplus0\oplus3=2$

数据范围与提示

对于 $30\%$ 的数据，$1\le n \leq 20$；

对于 $60\%$ 的数据，$1\le n \leq 5000$；

对于 $100\%$ 的数据，$1\le n \leq 2 \times 10^5$。