309630: CF1709E. XOR Tree
Memory Limit：256 MB
Time Limit：3 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
XOR Tree
题意翻译
你有一棵无根树，点数为 $n$，每个点有个点权 $a_u$，定义一条路径 $P(u,v)$ 的权值为经过的**所有点的点权的异或和**。定义一棵树是合法的，当且仅当树上所有**简单路径**（只经过每个点一次的路径）的的权值都不为 $0$。 你可以对权值进行修改，可以改成**任意正整数**，问最少修改多少次才能让这棵树合法。 输出最小修改次数。 $n\leq 2\times 10^5,a_i\leq 2^{30}$题目描述
You are given a tree consisting of $ n $ vertices. A number is written on each vertex; the number on vertex $ i $ is equal to $ a_i $ . Recall that a simple path is a path that visits each vertex at most once. Let the weight of the path be the bitwise XOR of the values written on vertices it consists of. Let's say that a tree is good if no simple path has weight $ 0 $ . You can apply the following operation any number of times (possibly, zero): select a vertex of the tree and replace the value written on it with an arbitrary positive integer. What is the minimum number of times you have to apply this operation in order to make the tree good?输入输出格式
输入格式
The first line contains one integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of vertices. The second line contains $ n $ integers $ a_1 $ , $ a_2 $ , ..., $ a_n $ ( $ 1 \le a_i < 2^{30} $ ) — the numbers written on vertices. Then $ n - 1 $ lines follow, each containing two integers $ x $ and $ y $ ( $ 1 \le x, y \le n; x \ne y $ ) denoting an edge connecting vertex $ x $ with vertex $ y $ . It is guaranteed that these edges form a tree.
输出格式
Print a single integer — the minimum number of times you have to apply the operation in order to make the tree good.
输入输出样例
输入样例 #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说明
In the first example, it is enough to replace the value on the vertex $ 1 $ with $ 13 $ , and the value on the vertex $ 4 $ with $ 42 $ .Input
题意翻译
你有一棵无根树，点数为 $n$，每个点有个点权 $a_u$，定义一条路径 $P(u,v)$ 的权值为经过的**所有点的点权的异或和**。定义一棵树是合法的，当且仅当树上所有**简单路径**（只经过每个点一次的路径）的的权值都不为 $0$。 你可以对权值进行修改，可以改成**任意正整数**，问最少修改多少次才能让这棵树合法。 输出最小修改次数。 $n\leq 2\times 10^5,a_i\leq 2^{30}$Output
**XOR Tree**
**题目大意：**
给定一棵无根树，有 $n$ 个节点，每个节点上有一个权值 $a_u$。定义一条路径 $P(u,v)$ 的权值为路径上所有节点权值的异或和。若一棵树上所有简单路径（每个节点只经过一次的路径）的权值都不为 $0$，则称该树为合法的。你可以将节点权值修改为任意正整数，问最少修改多少次可以使树合法。输出最小修改次数。
约束条件：$n \leq 2 \times 10^5, a_i \leq 2^{30}$
**输入输出格式：**
**输入格式：**
- 第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$）——节点的数量。
- 第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 \leq a_i < 2^{30}$）——每个节点上的数字。
- 接下来 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$（$1 \leq x, y \leq n; x \neq 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$ 就足够了。**XOR Tree** **题目大意：** 给定一棵无根树，有 $n$ 个节点，每个节点上有一个权值 $a_u$。定义一条路径 $P(u,v)$ 的权值为路径上所有节点权值的异或和。若一棵树上所有简单路径（每个节点只经过一次的路径）的权值都不为 $0$，则称该树为合法的。你可以将节点权值修改为任意正整数，问最少修改多少次可以使树合法。输出最小修改次数。 约束条件：$n \leq 2 \times 10^5, a_i \leq 2^{30}$ **输入输出格式：** **输入格式：** - 第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$）——节点的数量。 - 第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 \leq a_i < 2^{30}$）——每个节点上的数字。 - 接下来 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$（$1 \leq x, y \leq n; x \neq 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$ 就足够了。
**题目大意：**
给定一棵无根树，有 $n$ 个节点，每个节点上有一个权值 $a_u$。定义一条路径 $P(u,v)$ 的权值为路径上所有节点权值的异或和。若一棵树上所有简单路径（每个节点只经过一次的路径）的权值都不为 $0$，则称该树为合法的。你可以将节点权值修改为任意正整数，问最少修改多少次可以使树合法。输出最小修改次数。
约束条件：$n \leq 2 \times 10^5, a_i \leq 2^{30}$
**输入输出格式：**
**输入格式：**
- 第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$）——节点的数量。
- 第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 \leq a_i < 2^{30}$）——每个节点上的数字。
- 接下来 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$（$1 \leq x, y \leq n; x \neq 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$ 就足够了。**XOR Tree** **题目大意：** 给定一棵无根树，有 $n$ 个节点，每个节点上有一个权值 $a_u$。定义一条路径 $P(u,v)$ 的权值为路径上所有节点权值的异或和。若一棵树上所有简单路径（每个节点只经过一次的路径）的权值都不为 $0$，则称该树为合法的。你可以将节点权值修改为任意正整数，问最少修改多少次可以使树合法。输出最小修改次数。 约束条件：$n \leq 2 \times 10^5, a_i \leq 2^{30}$ **输入输出格式：** **输入格式：** - 第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$）——节点的数量。 - 第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 \leq a_i < 2^{30}$）——每个节点上的数字。 - 接下来 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$（$1 \leq x, y \leq n; x \neq 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$ 就足够了。