A16505. Boxed Like a Fish
编程题
提高+/省选-
知识点
题目描述
[Elite Four Battle Theme — Junichi Masuda, Pokémon Black & White](https://www.youtube.com/watch?v=llnXhrCn9Yo)
给定两个正整数 $n$ 和 $k$。你得到了一棵有 $n$ 个顶点的树（见注释$^*$），编号为 $1, \ldots, n$。
Cyndaquil 正在遍历这棵树，并试图到达某个叶子节点$^{\dagger}$。起初，他从一个非叶子节点 $v$ 出发，在他的每一步中，他可以选择原地不动，或者从顶点 $v$ 沿一条边移动到任意一个邻接点 $u$。
然而，Snorlax 试图阻止 Cyndaquil，通过在某一条边上“睡觉”来封锁这条边。当他选择一条边时，Cyndaquil 就无法穿过这条边，直到 Snorlax 再次移动。此外，每次只能有一条边被封锁，即只有最近选择的那条边被封锁。
当然，Snorlax 行动迟缓，他在选下一条边前需要等待一段时间。他有一个冷却计时器，起始值为 $0$。只有当冷却计时器为 $0$ 或更小的时候，他才可以选择一条新边，但他也可以选择暂时不更换。当他切换到新边时，冷却计时器会被重置为 $k$。每当 Cyndaquil 行动一次（即便原地不动），冷却计时器都会减 $1$。
他们轮流行动，如上所述，Snorlax 先行动，且初始时没有封锁任何边。假设两人都采取最优策略，Cyndaquil 是否始终能在有限步内到达一个叶子节点？
$^*$ 一棵树是无环连通图。
$^{\dagger}$ 度数为 $1$ 的顶点被称作叶子节点。
给定两个正整数 $n$ 和 $k$。你得到了一棵有 $n$ 个顶点的树（见注释$^*$），编号为 $1, \ldots, n$。
Cyndaquil 正在遍历这棵树，并试图到达某个叶子节点$^{\dagger}$。起初，他从一个非叶子节点 $v$ 出发，在他的每一步中，他可以选择原地不动，或者从顶点 $v$ 沿一条边移动到任意一个邻接点 $u$。
然而，Snorlax 试图阻止 Cyndaquil，通过在某一条边上“睡觉”来封锁这条边。当他选择一条边时，Cyndaquil 就无法穿过这条边，直到 Snorlax 再次移动。此外，每次只能有一条边被封锁，即只有最近选择的那条边被封锁。
当然，Snorlax 行动迟缓，他在选下一条边前需要等待一段时间。他有一个冷却计时器，起始值为 $0$。只有当冷却计时器为 $0$ 或更小的时候，他才可以选择一条新边，但他也可以选择暂时不更换。当他切换到新边时，冷却计时器会被重置为 $k$。每当 Cyndaquil 行动一次（即便原地不动），冷却计时器都会减 $1$。
他们轮流行动，如上所述，Snorlax 先行动，且初始时没有封锁任何边。假设两人都采取最优策略，Cyndaquil 是否始终能在有限步内到达一个叶子节点？
$^*$ 一棵树是无环连通图。
$^{\dagger}$ 度数为 $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$。
每个测试用例的第一行包含三个整数 $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$。
输出格式
对于每个测试用例，输出一行 "YES" 或 "NO"，表示 Cyndaquil 是否一定可以在有限步内到达一个叶子节点。
你的输出可以不区分大小写。例如 "yEs"、"yes"、"Yes"、"YES" 都会被判为正解。
你的输出可以不区分大小写。例如 "yEs"、"yes"、"Yes"、"YES" 都会被判为正解。
输入输出样例
输入 #1
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
输出 #1
YES NO YES NO NO YES
说明/提示
在第一个测试用例中，树结构如下：
Cyndaquil 从顶点 $1$ 出发。如果 Snorlax 封锁从 $1$ 到 $2$ 的边，则 Cyndaquil 可以在两步后到达顶点 $6$，这是一个叶子节点。否则，Cyndaquil 可以前进到顶点 $2$，从此 Snorlax 无法阻止他到达顶点 $3$ 或 $4$ 中的至少一个。
在第二个测试用例中，树结构如下：
可以证明 Snorlax 能够无限期地阻止 Cyndaquil 到达叶子节点 $1$ 或 $7$。
Cyndaquil 从顶点 $1$ 出发。如果 Snorlax 封锁从 $1$ 到 $2$ 的边，则 Cyndaquil 可以在两步后到达顶点 $6$，这是一个叶子节点。否则，Cyndaquil 可以前进到顶点 $2$，从此 Snorlax 无法阻止他到达顶点 $3$ 或 $4$ 中的至少一个。
在第二个测试用例中，树结构如下：
可以证明 Snorlax 能够无限期地阻止 Cyndaquil 到达叶子节点 $1$ 或 $7$。