P4186 [USACO18JAN] Cow at Large G

题目描述

最后，Bessie 被迫去了一个远方的农场。这个农场包含 $N$ 个谷仓（$2 \le N \le 10^5$）和 $N-1$ 条连接两个谷仓的双向隧道，所以每两个谷仓之间都有唯一的路径。每个只与一条隧道相连的谷仓都是农场的出口。当早晨来临的时候，Bessie 将在某个谷仓露面，然后试图到达一个出口。

但当 Bessie 露面的时候，她的位置就会暴露。一些农民在那时将从不同的出口谷仓出发尝试抓住 Bessie。农民和 Bessie 的移动速度相同（在每个单位时间内，每个农民都可以从一个谷仓移动到相邻的一个谷仓，同时 Bessie 也可以这么做）。农民们和 Bessie 总是知道对方在哪里。如果在任意时刻，某个农民和 Bessie 处于同一个谷仓或在穿过同一个隧道，农民就可以抓住 Bessie。反过来，如果 Bessie 在农民们抓住她之前到达一个出口谷仓，Bessie 就可以逃走。

Bessie 不确定她成功的机会，这取决于被雇佣的农民的数量。给定 Bessie 露面的谷仓K，帮助 Bessie 确定为了抓住她所需要的农民的最小数量。假定农民们会自己选择最佳的方案来安排他们出发的出口谷仓。

输入格式

输入的第一行包含 $N$ 和 $K$。接下来的 $N - 1$ 行，每行有两个整数（在 $1\sim N$ 范围内）描述连接两个谷仓的一条隧道。

输出格式

输出为了确保抓住 Bessie 所需的农民的最小数量。

由 @Marser 提供翻译

输入输出样例 1

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

3