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$ 时边权 $\operatorname{xor}$ 和为 $0$。 $1\le n\le 10^5$。