← 返回题目列表

Codeforces · 2207/D

D. 像鱼一样装箱

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

精英四人对战主题 — 增田顺一,神奇宝贝黑与白

令 $$$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 是否总能在有限的圈数内到达叶子。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是", "是“,和”是”将被视为积极响应。

示例

输入
复制

6
6 2 1
1 2
2 3
2 4
1 5
5 6
7 1 4
1 2
2 3
3 4
4 5
5 6
6 7
3 1 3
1 3
2 3
4 1 4
1 3
3 4
4 2
9 3 5
4 5
5 6
4 7
9 8
8 7
1 2
2 3
3 4
9 4 5
4 5
5 6
4 7
9 8
8 7
1 2
2 3
3 4

输出
复制

YES
NO
YES
NO
NO
YES

注意

在第一个测试用例中,树如下所示:

Cyndaquil 从顶点 $$$1$$$ 开始。如果 Snorlax 阻挡从 $$$1$$$ 到 $$$2$$$ 的边,那么 Cyndaquil 可以在两圈后到达顶点 $$$6$$$,这是一片叶子。否则,Cyndaquil 可以前进到顶点 $$$2$$$,从这里 Snorlax 无法阻止他到达顶点 $$$3$$$ 和 $$$4$$$ 中的至少一个。

在第二个测试用例中,树如下所示:

可以证明,Snorlax 可以无限期地阻止 Cyndaquil 到达叶子 $$$1$$$ 或 $$$7$$$。