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

输入 #1

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

输出 #1

2

输入输出样例 #2

输入 #2

4
2 1 1 1
1 2
1 3
1 4

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

2

说明/提示

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

由 ChatGPT 4.1 翻译