AT_arc116_e.[ARC116E] Spread of Information

高桥国有 $N$ 个城镇，分别命名为城镇 $1$、城镇 $2$、$\ldots$、城镇 $N$。这个国家有 $N-1$ 条道路，第 $i$ 条道路双向连接城镇 $u_i$ 和城镇 $v_i$。对于任意两个城镇 $a$ 和 $b$，都可以通过若干条道路从城镇 $a$ 到达城镇 $b$。

高桥国王打算将某条信息传遍全国。由于事务繁忙，国王最多只能直接将信息传达给 $K$ 个城镇。

国王完成信息传达的瞬间记为时刻 $0$。对于 $t=1,2,3,\cdots$，会发生如下现象：

• 对于通过一条道路直接相连的城镇对 $a$ 和 $b$，如果在时刻 $t-0.5$ 时城镇 $a$ 已经获得信息，而城镇 $b$ 尚未获得信息，则在时刻 $t$ 时城镇 $b$ 也会获得信息。

国王会合理选择 $K$ 个城镇作为信息的初始传递点，使得所有城镇获得信息所需的时间最小。请输出这个最小时间。

输入以如下格式从标准输入读入。

$N$ $K$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

请输出答案。

限制条件

• 输入均为整数。
• $1 \leq K < N \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N$
• 对于任意两个城镇 $a$ 和 $b$，都存在一条路径可以从 $a$ 到达 $b$。

样例解释 1

如果国王选择将信息直接传达给城镇 $2$ 和城镇 $4$，则城镇 $1$、$\ldots$、城镇 $5$ 首次获得信息的时刻分别为 $1, 0, 1, 0, 1$。此时，全国所有城镇都获得信息的最早时刻为 $1$，且可以证明这是最小可能值。

由 ChatGPT 4.1 翻译