题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

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$，表示道路直接连接的两个村庄编号。

输出格式

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

6 2
1 2
1 3
2 4
2 5
4 6

1

7 2
1 2
1 3
2 4
2 5
4 6
6 7

2

提示

样例 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 完成