SlavicG's Favorite Problem

题意翻译

给你一棵树和两个点 $a,b$，边有边权。你可以在任意时刻从当前所在的点跳到任意除了 $b$ 以外的点。求有没有方案使得从 $a$ 出发，到达 $b$ 时边权 $\operatorname{xor}$ 和为 $0$。 $1\le n\le 10^5$。

题目描述

You are given a weighted tree with $ n $ vertices. Recall that a tree is a connected graph without any cycles. A weighted tree is a tree in which each edge has a certain weight. The tree is undirected, it doesn't have a root. Since trees bore you, you decided to challenge yourself and play a game on the given tree. In a move, you can travel from a node to one of its neighbors (another node it has a direct edge with). You start with a variable $ x $ which is initially equal to $ 0 $ . When you pass through edge $ i $ , $ x $ changes its value to $ x ~\mathsf{XOR}~ w_i $ (where $ w_i $ is the weight of the $ i $ -th edge). Your task is to go from vertex $ a $ to vertex $ b $ , but you are allowed to enter node $ b $ if and only if after traveling to it, the value of $ x $ will become $ 0 $ . In other words, you can travel to node $ b $ only by using an edge $ i $ such that $ x ~\mathsf{XOR}~ w_i = 0 $ . Once you enter node $ b $ the game ends and you win. Additionally, you can teleport at most once at any point in time to any vertex except vertex $ b $ . You can teleport from any vertex, even from $ a $ . Answer with "YES" if you can reach vertex $ b $ from $ a $ , and "NO" otherwise. Note that $ \mathsf{XOR} $ represents the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. The first line of each test case contains three integers $ n $ , $ a $ , and $ b $ ( $ 2 \leq n \leq 10^5 $ ), ( $ 1 \leq a, b \leq n; a \ne b $ ) — the number of vertices, and the starting and desired ending node respectively. Each of the next $ n-1 $ lines denotes an edge of the tree. Edge $ i $ is denoted by three integers $ u_i $ , $ v_i $ and $ w_i $ — the labels of vertices it connects ( $ 1 \leq u_i, v_i \leq n; u_i \ne v_i; 1 \leq w_i \leq 10^9 $ ) and the weight of the respective edge. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case output "YES" if you can reach vertex $ b $ , and "NO" otherwise.

输入输出样例

输入样例 #1

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

输出样例 #1

YES
NO
YES

说明

For the first test case, we can travel from node $ 1 $ to node $ 3 $ , $ x $ changing from $ 0 $ to $ 1 $ , then we travel from node $ 3 $ to node $ 2 $ , $ x $ becoming equal to $ 3 $ . Now, we can teleport to node $ 3 $ and travel from node $ 3 $ to node $ 4 $ , reaching node $ b $ , since $ x $ became equal to $ 0 $ in the end, so we should answer "YES". For the second test case, we have no moves, since we can't teleport to node $ b $ and the only move we have is to travel to node $ 2 $ which is impossible since $ x $ wouldn't be equal to $ 0 $ when reaching it, so we should answer "NO".

**题意翻译**

给你一棵树和两个点 $a, b$，边有边权。你可以在任意时刻从当前所在的点跳到任意除了 $b$ 以外的点。求有没有方案使得从 $a$ 出发，到达 $b$ 时边权 $\oplus$ 和为 $0$。

$1 \le n \le 10^5$。

**题目描述**

给定一个带权重的树，有 $n$ 个顶点。回忆一下，树是一个没有环的连通图。在带权树中，每条边都有一定的权重。树是无向的，它没有根。

由于树让你感到无聊，你决定挑战自己，在给定的树上玩一个游戏。

每次移动，你可以从节点走到其邻居之一（与它有直接边相连的节点）。

你从一个变量 $x$ 开始，初始值为 $0$。当你经过边 $i$ 时，$x$ 的值变为 $x \oplus w_i$（其中 $w_i$ 是第 $i$ 条边的权重）。

你的任务是 从顶点 $a$ 走到顶点 $b$，但你只能在旅行到它之后，$x$ 的值变为 $0$ 时进入节点 $b$。换句话说，你只能通过使用边 $i$ 使得 $x \oplus w_i = 0$ 来到达节点 $b$。一旦你进入节点 $b$，游戏结束，你就赢了。

此外，你可以在任何时候最多传送一次到除了节点 $b$ 以外的任何节点。你可以从任何节点传送，甚至可以从 $a$。

如果能从 $a$ 到达 $b$，回答 "YES"，否则回答 "NO"。

注意 $\oplus$ 表示按位异或操作。

**输入输出格式**

**输入格式**

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）——测试用例的数量。

每个测试用例的第一行包含三个整数 $n$，$a$ 和 $b$（$2 \leq n \leq 10^5$），（$1 \leq a, b \leq n; a \ne b$）——顶点的数量以及起始和期望的结束节点。

接下来的 $n-1$ 行描述了树的一条边。边 $i$ 由三个整数 $u_i$，$v_i$ 和 $w_i$ 表示——它连接的顶点的标签（$1 \leq u_i, v_i \leq n; u_i \ne v_i; 1 \leq w_i \leq 10^9$）以及相应边的权重。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

**输出格式**

对于每个测试用例，如果能到达顶点 $b$，输出 "YES"，否则输出 "NO"。

**输入输出样例**

**输入样例 #1**

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

**输出样例 #1**

```
YES
NO
YES
```

**说明**

对于第一个测试用例，我们可以从节点 $1$ 走到节点 $3$，$x$ 从 $0$ 变为 $1$，然后我们从节点 $3$ 走到节点 $2$，$x$ 变为 $3$。现在，我们可以传送到节点 $3$ 并从节点 $3$ 走到节点 $4$，到达节点 $b$，因为最后 $x$ 变为 $0$，所以我们应该回答 "YES"。

对于第二个测试用例，我们无法移动，因为我们不能传送到节点 $b$，我们唯一可以移动的是走到节点 $2$，这是不可能的，因为到达它时 $x$ 不会等于 $0$，所以我们应该回答 "NO"。**题意翻译** 给你一棵树和两个点 $a, b$，边有边权。你可以在任意时刻从当前所在的点跳到任意除了 $b$ 以外的点。求有没有方案使得从 $a$ 出发，到达 $b$ 时边权 $\oplus$ 和为 $0$。 $1 \le n \le 10^5$。 **题目描述** 给定一个带权重的树，有 $n$ 个顶点。回忆一下，树是一个没有环的连通图。在带权树中，每条边都有一定的权重。树是无向的，它没有根。 由于树让你感到无聊，你决定挑战自己，在给定的树上玩一个游戏。 每次移动，你可以从节点走到其邻居之一（与它有直接边相连的节点）。 你从一个变量 $x$ 开始，初始值为 $0$。当你经过边 $i$ 时，$x$ 的值变为 $x \oplus w_i$（其中 $w_i$ 是第 $i$ 条边的权重）。 你的任务是 从顶点 $a$ 走到顶点 $b$，但你只能在旅行到它之后，$x$ 的值变为 $0$ 时进入节点 $b$。换句话说，你只能通过使用边 $i$ 使得 $x \oplus w_i = 0$ 来到达节点 $b$。一旦你进入节点 $b$，游戏结束，你就赢了。 此外，你可以在任何时候最多传送一次到除了节点 $b$ 以外的任何节点。你可以从任何节点传送，甚至可以从 $a$。 如果能从 $a$ 到达 $b$，回答 "YES"，否则回答 "NO"。 注意 $\oplus$ 表示按位异或操作。 **输入输出格式** **输入格式** 第一行包含一个整数 $t$（$1 \leq t \leq 1000$）——测试用例的数量。 每个测试用例的第一行包含三个整数 $n$，$a$ 和 $b$（$2 \leq n \leq 10^5$），（$1 \leq a, b \leq n; a \ne b$）——顶点的数量以及起始和期望的结束节点。 接下来的 $n-1$ 行描述了树的一条边。边 $i$ 由三个整数 $u_i$，$v_i$ 和 $w_i$ 表示——它连接的顶点的标签（$1 \leq u_i, v_i \leq n; u_i \ne v_i; 1 \leq w_i \leq 10^9$）以及相应边的权重。 保证所有测试用例的 $n$ 之和不超过 $10^5$。 **输出格式** 对于每个测试用例，如果能到达顶点 $b$，输出 "YES"，否则输出 "NO"。 **输入输出样例** **输入样例 #1** ``` 3 5 1 4 1 3 1 2 3 2 4 3 3 3 5 1 2 1 2 1 2 2 6 2 3 1 2 1 2 3 1 3 4 1 4 5 3 5 6 5 ``` **输出样例 #1** ``` YES NO YES ``` **说明** 对于第一个测试用例，我们可以从节点 $1$ 走到节点 $3$，$x$ 从 $0$ 变为 $1$，然后我们从节点 $3$ 走到节点 $2$，$x$ 变为 $3$。现在，我们可以传送到节点 $3$ 并从节点 $3$ 走到节点 $4$，到达节点 $b$，因为最后 $x$ 变为 $0$，所以我们应该回答 "YES"。 对于第二个测试用例，我们无法移动，因为我们不能传送到节点 $b$，我们唯一可以移动的是走到节点 $2$，这是不可能的，因为到达它时 $x$ 不会等于 $0$，所以我们应该回答 "NO"。