P12659 [KOI 2023 Round 1] 加油站

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

KOI 国家由 $N$ 个村庄组成。每个村庄从 1 到 $N$ 编号。国家中共有 $N - 1$ 条道路，每条道路连接两个不同的村庄，编号从 1 到 $N - 1$。第 $i$ 条道路连接的是第 $x_i$ 个村庄与第 $y_i$ 个村庄。 KOI 国家中的任意两个村庄之间，恰好存在一条路径将它们连接起来。 从第 $x$ 个村庄到第 $y$ 个村庄的路径可以表示为一个村庄序列：$x$ - $z_1$ - $z_2$ - ⋯ - $z_t$ - $y$，该路径满足以下两个条件： - 路径上相邻两个村庄之间，即 $x$ 与 $z_1$，$z_1$ 与 $z_2$，⋯，$z_t$ 与 $y$ 之间都存在道路直接连接。 - 路径中不得有重复村庄。也就是说，$x$，$z_1$，⋯，$z_t$，$y$ 均为互不相同的村庄。 路径的“长度”定义为该路径上所经过的道路数，即 $t + 1$。 现在，计划在若干个村庄中设置加油站。根据 KOI 国家法律，加油站必须满足以下条件： - 对于任意长度为 $k$ 的路径，路径中必须至少有一个村庄设有加油站。 在满足上述条件的前提下，找出设置加油站所需的最小数量。

第一行包含两个整数 $N$ 和 $k$，以空格分隔，表示村庄的数量与路径长度限制。 接下来 $N - 1$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示道路直接连接的两个村庄编号。

输出一行，表示满足条件所需的最少加油站数量。

**样例 1 说明** 只需在第 $2$ 个村庄设置加油站即可满足所有长度为 $2$ 的路径。 **样例 2 说明** 仅在第 $2$ 个村庄设置加油站不能满足所有长度为 $2$ 的路径（例如路径 $4-6-7$ 不包含加油站）。若再在第 $6$ 个村庄也设置加油站，则所有长度为 $2$ 的路径都包含至少一个加油站。因此最小加油站数量为 $2$。 **限制条件** - 所有输入均为整数。 - $2 \leq N \leq 200\,000$ - $1 \leq k \leq N - 1$ - $1 \leq x_i, y_i \leq N$ - $x_i \ne y_i$ - 任意两个村庄之间，存在唯一一条路径相连。 - 至少存在一条长度为 $k$ 的路径。 **子问题** 1. （9 分）对于每条道路 $i$（$1 \leq i \leq N - 1$），连接的是第 $i$ 个村庄和第 $i + 1$ 个村庄。 2. （10 分）$k = 1$ 3. （11 分）对于每条道路 $i$（$1 \leq i \leq N - 1$），连接的是第 $i + 1$ 个村庄和 $\lfloor \frac{i + 1}{2} \rfloor$ 个村庄。这里 $\lfloor x \rfloor$ 表示不大于 $x$ 的最大整数。 4. （12 分）$N \leq 15$ 5. （15 分）$N \leq 300$ 6. （17 分）$N \leq 3\,000$ 7. （26 分）无额外限制 翻译由 ChatGPT-4o 完成