题目描述

给定一棵有 $n$ 个顶点的带权树。树是一个无环连通图。带权树是指每条边都有一个权值的树。该树是无向的，没有根节点。

由于你觉得树太无聊了，于是你决定在这棵树上玩一个游戏。

每一步，你可以从当前节点移动到它的一个邻居（即与其直接相连的另一个节点）。

你有一个变量 $x$，初始值为 $0$。每当你经过第 $i$ 条边时，$x$ 会变为 $x~\mathsf{XOR}~w_i$（其中 $w_i$ 是第 $i$ 条边的权值）。

你的任务是从顶点 $a$ 走到顶点 $b$，但只有当你到达 $b$ 时，$x$ 的值变为 $0$ 时才能进入节点 $b$。换句话说，你只能通过一条边 $i$ 进入节点 $b$，且 $x~\mathsf{XOR}~w_i = 0$。一旦你进入节点 $b$，游戏立即结束，你就获胜了。

此外，你最多可以在任意时刻传送一次到任意一个顶点（除了 $b$）。你可以从任意节点（包括 $a$）进行传送。

如果你能从 $a$ 到达 $b$，输出 "YES"，否则输出 "NO"。

注意，$\mathsf{XOR}$ 表示按位异或运算。

输入格式

第一行包含一个整数 $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$ 行，每行包含三个整数 $u_i$、$v_i$ 和 $w_i$，表示第 $i$ 条边连接的两个顶点（$1 \leq u_i, v_i \leq n; u_i \ne v_i; 1 \leq w_i \leq 10^9$）以及该边的权值。

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

输出格式

对于每个测试用例，若你能从 $a$ 到达 $b$，输出 "YES"；否则输出 "NO"。

样例

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

YES
NO
YES

样例说明

对于第一个测试用例，我们可以从节点 $1$ 走到节点 $3$，$x$ 从 $0$ 变为 $1$，然后从节点 $3$ 走到节点 $2$，$x$ 变为 $3$。此时，我们可以传送到节点 $3$，再从节点 $3$ 走到节点 $4$，最终到达节点 $b$，因为此时 $x$ 变为 $0$，所以答案是 "YES"。

对于第二个测试用例，我们没有可行的操作，因为不能传送到节点 $b$，且唯一能走的就是到节点 $2$，但此时 $x$ 不等于 $0$，所以答案是 "NO"。

由 ChatGPT 4.1 翻译

来源

Codeforces 1760G，英文题名 SlavicG's Favorite Problem。