← 返回题目列表

AtCoder · arc116_e

E. 信息传播

中文机器翻译题面 查看原题

分数: 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