Cow at Large

题目描述

最终走投无路的 Bessie 躲进了一个偏远农场。该农场由 $N$ 个谷仓（$2 \leq N \leq 10^5$）以及 $N-1$ 条连接谷仓的双向隧道组成，因此任意两座谷仓之间都存在唯一的一条路径。任何只连接一条隧道的谷仓都是一个出口。 当早晨来临时，Bessie 会在某个谷仓现身，并试图到达某个出口。 但在 Bessie 现身的那一刻，执法人员就能精确定位她的位置。随后一些农夫会从若干出口谷仓出发，尝试抓住 Bessie。农夫与 Bessie 的移动速度相同（因此在每个时间步中，每个农夫都可以从一个谷仓移动到相邻的一个谷仓）。农夫始终知道 Bessie 的位置，Bessie 也始终知道农夫的位置。 如果在任何时刻，某个农夫与 Bessie 位于同一个谷仓，或与 Bessie 正在穿过同一条隧道，则农夫抓住了 Bessie。相反，如果 Bessie 在任何农夫抓住她之前到达某个出口谷仓，则 Bessie 成功逃脱。 Bessie 不确定自己成功的概率，这取决于执法人员能够部署的农夫数量。已知 Bessie 在谷仓 $K$ 现身，请帮助 Bessie 确定：在农夫以最优方式分布在各个出口谷仓的前提下，确保抓住 Bessie 所需的最少农夫数量。

输入格式

第一行输入包含 $N$ 和 $K$。接下来的 $N-1$ 行每行给出两个整数，范围均为 $1 \ldots N$，描述一条连接两座谷仓的隧道。

输出格式

请输出确保抓住 Bessie 所需的最少农夫数量。

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

3

提示

题目致谢：Dhruv Rohatgi

标签: USACO|2018|Gold

来源

USACO|2018|Gold