← 返回题目列表

Codeforces · 1760/G

G. SlavicG 最喜欢的问题

中文机器翻译题面 查看原题

给你一棵带有 $$$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$$$,则回答“是”,否则回答“否”。

请注意,$$$\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$$$ 行表示树的一条边。边 $$$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”。