← 返回题目列表

Codeforces · 1381/D

D. 雄伟的棕色树蛇

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

有一个由 $$$n$$$ 个顶点组成的无向树,由 $$$n-1$$$ 双向边连接。这棵树里还有一条蛇。它的头位于顶点$$$a$$$,尾部位于顶点$$$b$$$。蛇的身体占据了 $$$a$$$ 和 $$$b$$$ 之间唯一简单路径上的所有顶点。

蛇想知道它是否可以反转自己 - 也就是说,将其头部移动到其尾巴开始的位置,并将其尾巴移动到其头部开始的位置。不幸的是,蛇的运动受到树结构的限制。

在操作中,蛇可以将其头部移动到当前未被蛇占据的相邻顶点。当它这样做时,尾巴会向头部移动一个顶点,从而使蛇的长度保持不变。类似地,蛇也可以将其尾巴移动到当前未被蛇占据的相邻顶点。当它这样做时,头部会向尾部移动一个单位。

让我们用 $$$(h,t)$$$ 表示蛇的位置,其中 $$$h$$$ 是蛇头顶点的索引,$$$t$$$ 是蛇尾顶点的索引。这条蛇可以通过$$$(4,7)\to (5,1)\to (4,2)\to (1, 3)\to (7,2)\to (8,1)\to (7,4)$$$的运动来反转自己。

确定是否可以通过某些操作序列反转蛇。

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 100$$$) — 测试用例的数量。接下来的几行包含测试用例的描述。

每个测试用例的第一行包含三个整数 $$$n,a,b$$$ ($$$2\le n\le 10^5,1\le a,b\le n,a\ne b$$$)。

接下来的 $$$n-1$$$ 行包含两个整数 $$$u_i,v_i$$$ ($$$1\le u_i,v_i\le n,u_i\ne v_i$$$),表示顶点 $$$u_i$$$ 和 $$$v_i$$$ 之间的一条边。保证给定的边形成一棵树。

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

输出

对于每个测试用例,如果蛇有可能反转,则输出“YES”,否则输出“NO”。

示例

输入 #1

4
8 4 7
1 2
2 3
1 4
4 5
4 6
1 7
7 8
4 3 2
4 3
1 2
2 3
9 3 5
1 2
2 3
3 4
1 5
5 6
6 7
1 8
8 9
16 15 12
1 2
2 3
1 4
4 5
5 6
6 7
4 8
8 9
8 10
10 11
11 12
11 13
13 14
10 15
15 16

输出 #1

YES
NO
NO
YES

注意

第一个测试用例如上图所示。

在第二个测试用例中,树是一条路径。我们可以证明蛇不能逆转自己。

在第三个测试用例中,我们可以证明蛇无法反转自身。

在第四个测试用例中,示例解决方案是:

$$$(15,12)\至(16,11)\至(15,13)\至(10,14)\至(8,13)\至(4,11)\至(1,10)$$$

$$$\到(2,8)\到(3,4)\到(2,5)\到(1,6)\到(4,7)\到(8,6)\到(10,5)$$$

$$$\到(11,4)\到(13,8)\到(14,10)\到(13,15)\到(11,16)\到(12,15)$$$。