题目描述

高橋国には $N$ 箇所の町があり、それぞれ町 $1$ 、町 $2$、 $\ldots$ 、町 $N$ と名付けられています。 この国には $N-1$ 本の道があり、 $i$ 本目の道は 町 $u_i$ と町 $v_i$ を双方向に結びます。任意の $2$ つの町 $a$, $b$ について、いくつかの道を通ることにより、町 $a$ から町 $b$ へ移動することが出来ます。

高橋国王は、ある情報を国土全体に流そうとしています。多忙な高橋国王は、 $K$ 箇所までの町にしか直接情報を伝達することが出来ません。

高橋国王の情報伝達が終わった瞬間を時刻 $0$ とします。 $t\ =\ 1,\ 2,\ 3,\ \cdots$ について、以下の現象が発生します。

• $1$ 本の道で直接結ばれている町の組 $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}$

输出格式

答えを出力せよ。

题目大意

• 给定一棵 $N$ 个点的树。
• 要求在树上选择 $K$ 个关键点 $p_1,p_2,\dots,p_K$，使得 $\max\limits_{i=1}^N\min\limits_{j=1}^K dis(i,p_j)$ 最小。其中 $dis(i,p_j)$ 是指树上 $i$ 到 $p_j$ 的最短路径经过的边数。
• 数据范围：$1\le K<N\le 2\times 10^5$。
• Translated by pitham（脾土蛤蟆）。

5 2
1 2
2 3
3 4
4 5

1

5 1
1 2
1 3
1 4
5 4

2

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

提示

制約

• 入力は全て整数
• $1\ \leq\ K\ <\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ u_i,\ v_i\ \leq\ N$
• 任意の $2$ つの町 $a$, $b$ について、いくつかの道を通ることにより、町 $a$ から町 $b$ へ移動することが出来る。

Sample Explanation 1

高橋国王が町 $2$ と町 $4$ に直接情報を伝達した場合、町 $1$ 、 $\ldots$ 、町$5$ に初めて情報が伝わる時刻は、それぞれ $1,\ 0,\ 1,\ 0,\ 1$ となります。このとき、 国土全体に情報が広まるのは時刻 $1$ であり、これが達成可能な最小値であることが証明出来ます。