J10 实践-5 SlavicG最爱的问题

题目描述

给你一棵有 $n$ 个顶点的加权树。回顾一下，树是一个没有任何循环的连接图。加权树是一棵树，其中每条边都有一定的权重。这棵树是无定向的，它没有根。

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

在一次移动中，你可以从一个节点移动到它的一个邻居（与它有直接边的另一个节点）。

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

你的任务是从顶点 $a$ 到顶点 $b$，但你被允许进入节点 $b$，当且仅当旅行到它之后，$x$ 的值将变成 $0$。换句话说，你只能通过使用边 $i$，使 $x\ XOR\ wi=0$ 来旅行到节点 $b$。

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

如果你能从 $a$ 到达顶点 $b$，就回答 "是"，否则回答 "否"。

输入格式

第一行包含一个整数 $t$--测试数据的组数。

每个测试组的第一行包含三个整数 $n$、$a$ 和 $b$--顶点的数量，以及分别是起始节点和期望的结束节点。

接下来的 $n-1$ 行中的每一行表示树的一条边。边 $i$ 由三个整数 $u_i$、$v_i$ 和 $w_i$表示--它连接的顶点的编号和边的权重。

输出格式

对于每个测试案例，如果你能到达顶点 $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$ ，这是不可能的，因为到达节点 $2$ 时 $x$ 不会等于 $0$，所以我们应该回答 "NO"。

数据范围

对于 $100\%$ 的数据，$1 \le t \le 1000$ ，$2 \le n \le 10^5$，$1 \le a,b \le n,a \ne b$，$1 \le u_i,v_i \le n,u_i \ne v_i$，$1 \le w_i \le 10^9$ ，可以保证所有测试案例的 $n$ 之和不超过 $10^5$。