P6499 [COCI 2016/2017 #2] Burza

Daniel 和 Stjepan 在一棵含有 $n$ 个节点的树上做游戏，树上各节点的编号为 $1,2,\dots,n$。游戏开始时，$1$ 号节点上有一枚硬币。 游戏规则如下： 1. Daniel 选择一个节点，将其标记。 2. Stjepan 标记当前硬币所在的节点。 3. Stjepan 将硬币移至一个**尚未标记**且**与当前所在的节点相邻**的节点。 重复以上操作。当 Stjepan 无法移动硬币时，游戏结束。 Daniel 想知道是否存在某种**既定**的操作策略，使得**无论 Stjepan 如何操作**，都能在 $k$ 轮操作内结束游戏。即 Stjepan 能移动硬币的次数**小于** $k$。

无

无

#### 【样例解释】 **样例 2 解释** - 若 Daniel 标记结点 $1$，Stjepan 可以将硬币移至结点 $2$ 或结点 $3$。 - 若 Daniel 标记结点 $2$，Stjepan 可以将硬币移至结点 $3$。 - 若 Daniel 标记结点 $3$，Stjepan 可以将硬币移至结点 $2$。 均不能在 $1$ 轮操作内结束游戏。 即不存在满足条件的操作策略。 **样例 3 解释** - 第一轮操作，Daniel 标记结点 $2$。 - 第二轮操作，Daniel 标记结点 $6$。 无论 Stjepan 如何操作，都无法第二次移动硬币。 即存在满足条件的操作策略。 ------------ #### 【数据规模与约定】 对于 $100\%$ 的数据，$1\le k\le n\le 400$，$1\le a,b\le n$。 ------------ #### 【说明】 **题目译自 [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #2](https://hsin.hr/coci/archive/2016_2017/contest2_tasks.pdf) _T6 Burza_**。