| 精英四人对战主题 — 增田顺一,神奇宝贝黑与白 |
![]() |
令 $$$n, k$$$ 为正整数。给你一棵树$$$^{\text{*}}$$$,其$$$n$$$顶点编号为$$$1、\ldots、n$$$。
Cyndaquil 正在遍历这棵树,并试图到达其中一片叶子$$$^{\text{†}}$$$。最初,他从非叶子顶点 $$$v$$$ 开始,在一个回合中,他可以选择保持静止或从顶点 $$$v$$$ 沿一条边移动到其任何邻居 $$$u$$$。
然而,Snorlax 试图通过睡在边缘来阻止 Cyndaquil 这样做。当他选择一条边缘时,辛达奎尔将被阻止穿过它,直到卡诺拉克斯再次移动。此外,一次只能禁止一条边,因此只有最近选择的边被阻止。
当然,Snorlax 速度很慢,需要一些时间才能选择新的优势。他有一个冷却计时器,最初为 $$$0$$$。他只能在冷却时间为 $$$0$$$ 或更低时选择新的优势, 但他不必立即这样做。当他移动到新的边缘时,计时器将重置为$$$k$$$。 Cyndaquil 每回合后(即使他保持静止),冷却时间都会减少 $$$1$$$。
他们轮流行动,如前所述,Snorlax 首先开始,最初,他没有在任何边缘睡觉。假设两者都发挥最佳状态,Cyndaquil 在有限的回合后总能到达叶子吗?
$$$^{\text{*}}$$$树是没有环的连通图。
$$$^{\text{†}}$$$度数为 1 的顶点称为叶子。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$v$$$ ($$$3 \leq n \leq 5 \cdot 10^5$$$, $$$1 \leq k, v \leq n$$$) - 树中的顶点数、Snorlax 的冷却计时器和Cyndaquil 的起始顶点。
每个测试用例接下来的 $$$n-1$$$ 行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \leq a, b \leq n$$$, $$$a \neq b$$$),描述顶点 $$$a$$$ 和 $$$b$$$ 之间的边。保证这些边形成一棵树,并且 $$$v$$$ 不是叶子。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,打印一行包含“是“或”NO”,表示 Cyndaquil 是否总能在有限的圈数内到达叶子。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是", "是“,和”是”将被视为积极响应。
示例
输入复制
66 2 11 22 32 41 55 67 1 41 22 33 44 55 66 73 1 31 32 34 1 41 33 44 29 3 54 55 64 79 88 71 22 33 49 4 54 55 64 79 88 71 22 33 4
输出复制
YESNOYESNONOYES
注意
在第一个测试用例中,树如下所示:
![]() |
Cyndaquil 从顶点 $$$1$$$ 开始。如果 Snorlax 阻挡从 $$$1$$$ 到 $$$2$$$ 的边,那么 Cyndaquil 可以在两圈后到达顶点 $$$6$$$,这是一片叶子。否则,Cyndaquil 可以前进到顶点 $$$2$$$,从这里 Snorlax 无法阻止他到达顶点 $$$3$$$ 和 $$$4$$$ 中的至少一个。
在第二个测试用例中,树如下所示:
![]() |
可以证明,Snorlax 可以无限期地阻止 Cyndaquil 到达叶子 $$$1$$$ 或 $$$7$$$。


