CF2207D.Boxed Like a Fish

Elite Four Battle Theme — Junichi Masuda, Pokémon Black & White

Let $n, k$ be positive integers. You are given a tree$^{\text{∗}}$ with $n$ vertices numbered $1, \ldots, n$.

Cyndaquil is traversing this tree and is trying to reach one of its leaves$^{\text{†}}$. Initially, he starts at a non-leaf vertex $v$, and in one turn, he may either choose to stay still or move from a vertex $v$ along an edge to any of its neighbors $u$.

However, Snorlax is trying to stop Cyndaquil from doing this by sleeping on an edge. When he picks an edge, Cyndaquil is blocked from traversing it until Snorlax moves again. Furthermore, only one edge may be disallowed at a time, so that only the most recently chosen edge is blocked.

Of course, Snorlax is slow and needs some time before he can pick a new edge. He has a cooldown timer, initially at $0$. He may only choose a new edge when the cooldown is at $0$ or lower, but he doesn't have to do it immediately. When he moves to a new edge, the timer is reset to $k$. After each of Cyndaquil's turns (even if he stays still), the cooldown timer decreases by $1$.

They take turns acting as previously described, with Snorlax starting first, and initially, he is not sleeping on any edge. Assuming both of them play optimally, can Cyndaquil always reach a leaf after a finite number of turns?

$^{\text{∗}}$A tree is a connected graph without cycles.

$^{\text{†}}$A vertex with degree 1 is called a leaf.

精英四天王战斗主题曲 — 增田顺一，《宝可梦 黑／白》

设 $n, k$ 为正整数。给定一棵含 $n$ 个顶点（编号为 $1, \ldots, n$）的树$^{\text{∗}}$。

小火龙正在该树上移动，目标是抵达其中一个叶节点$^{\text{†}}$。初始时，它位于一个非叶顶点 $v$；在每一轮中，它可选择原地不动，或沿一条边从当前顶点 $v$ 移动至其任意一个邻接顶点 $u$。

然而，卡比兽试图通过睡在某条边上阻止小火龙达成目标。当它选定一条边后，小火龙便无法经过该边，直至卡比兽再次移动为止。此外，任意时刻至多只有一条边被禁止通行，即仅最近一次选定的边被封锁。

当然，卡比兽行动迟缓，在选定下一条边前需要一定的准备时间。它拥有一个初始值为 $0$ 的冷却计时器。仅当冷却值 $\leq 0$ 时，它才可选择一条新边（但并非必须立即执行）；一旦它更换所选边，计时器即重置为 $k$。在小火龙的每一轮行动（包括原地不动）结束后，冷却计时器减 $1$。

双方按上述规则轮流行动，卡比兽先行；初始时，它未睡在任何边上。若双方均采取最优策略，小火龙是否总能在有限轮次内抵达某个叶节点？

$^{\text{∗}}$ 树是一个无环的连通图。

$^{\text{†}}$ 度数为 $1$ 的顶点称为叶节点。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains three integers $n$, $k$, and $v$ ($3 \leq n \leq 5 \cdot 10^5$, $1 \leq k, v \leq n$) — the number of vertices in the tree, Snorlax's cooldown timer, and Cyndaquil's starting vertex.

The next $n-1$ lines of each test case contain two integers $a$ and $b$ ($1 \leq a, b \leq n$, $a \neq b$), describing an edge between vertices $a$ and $b$. It is guaranteed that these edges form a tree and that $v$ is not a leaf.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print a single line containing either "YES" or "NO", representing whether or not Cyndaquil can always reach a leaf in a finite number of turns.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

对于每个测试用例，输出一行，包含“YES”或“NO”，表示小火龙是否总能在有限步数内到达某个叶子节点。

你可以以任意大小写形式输出答案（大写或小写均可）。例如，字符串 “yEs”、“yes”、“Yes” 和 “YES” 均会被识别为肯定回答。

In the first test case, the tree is shown below:

Cyndaquil starts at vertex $1$. If Snorlax blocks the edge from $1$ to $2$, then Cyndaquil can reach vertex $6$ after two turns, which is a leaf. Otherwise, Cyndaquil can advance to vertex $2$, from which Snorlax cannot stop him from reaching at least one of vertices $3$ and $4$.

In the second test case, the tree is shown below:

It can be shown that Snorlax can block Cyndaquil indefinitely from reaching either leaf $1$ or $7$.

在第一个测试用例中，树的结构如下所示：

小火龙从顶点 $1$ 出发。若卡比兽封锁了从 $1$ 到 $2$ 的边，则小火龙经过两轮移动后可到达顶点 $6$（该顶点为叶子节点）。否则，小火龙可前进至顶点 $2$，此后卡比兽无法阻止小火龙抵达顶点 $3$ 或 $4$ 中的至少一个。

在第二个测试用例中，树的结构如下所示：

可以证明：卡比兽能够无限期地阻止小火龙抵达任意一个叶子节点（即节点 $1$ 或 $7$）。