分数: 800 点
问题陈述
高桥王国有 N 城镇,称为Town 1 通过 N。 有 N-1 这个王国的道路。的 i第条路连接城镇 u_i 和镇 v_i 双向。对于任意两个城镇 a 和 b,可以从城镇获得 a 到镇 b 穿过一些道路。
国王高桥想要在整个王国传播一些信息。由于他很忙,他最多可以直接将这些信息传送给 K 城镇。
假设高桥在某个时间完成信息传输 0。然后,对于每个 t = 1, 2, 3, \cdots,会发生以下情况:
- 对于城镇 a 和 b 由道路直接连接,如果 a 已及时收到信息 t - 0.5 但是 b 还没有, b 收到时间 t.
高桥想要选择 K 城镇传输信息,以尽量减少每个城镇收到信息所需的时间。找出这需要的最短时间。
约束
- 输入中的所有值都是整数。
- 1 \leq K < N \leq 2 \times 10^5
- 1 \leq u_i, v_i \leq N
- 对于任意两个城镇 a 和 b,可以从城镇获得 a 到镇 b 穿过一些道路。
输入
输入由标准输入按以下格式给出:
N K
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
输出
打印答案。
示例输入 1
5 2 1 2 2 3 3 4 4 5
示例输出 1
1
如果高桥直接将信息传输到镇 2 和 4, 镇 分别为 1, 2, 3, 4, 5 收到时间 1, 0, 1, 0, 1。 这样的话,信息一时间就传遍了整个王国 1。我们可以证明这是最早的时间。
示例输入 2
5 1 1 2 1 3 1 4 5 4
示例输出 2
2
示例输入 3
20 3 2 15 6 5 12 1 7 9 17 2 15 5 2 4 17 16 12 2 8 17 17 19 18 11 20 8 20 3 13 9 11 10 11 20 14 8 11 7
示例输出 3
3