E - Spread of Information 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MB

配点 : 800 点

問題文

高橋国には 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 箇所の連絡先を適切に選択し、全ての町に情報が伝わるまでに掛かる時間を最小化しようと考えています。最小値を答えてください。

制約

  • 入力は全て整数
  • 1 \leq K < N \leq 2 \times 10^5
  • 1 \leq u_i, v_i \leq N
  • 任意の 2 つの町 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 、 \ldots 、町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

Score : 800 points

Problem Statement

Takahashi Kingdom has N towns, called Town 1 through N. There are N-1 roads in this kingdom. The i-th road connects Town u_i and Town v_i bidirectionally. For any two towns a and b, it is possible to get from Town a to Town b by traversing some roads.

Takahashi, the king, wants to spread some information all over the kingdom. Since he is busy, he can directly transmit this information to at most K towns.

Assume that Takahashi finishes transmitting the information at time 0. Then, for each t = 1, 2, 3, \cdots, the following happens:

  • For towns a and b directly connected by a road, if a has already received the information at time t - 0.5 but b has not, b receives it at time t.

Takahashi wants to choose the K towns to transmit the information to minimize the time taken until every town receives it. Find the minimum time this takes.

Constraints

  • All values in input are integers.
  • 1 \leq K < N \leq 2 \times 10^5
  • 1 \leq u_i, v_i \leq N
  • For any two towns a and b, it is possible to get from Town a to Town b by traversing some roads.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

5 2
1 2
2 3
3 4
4 5

Sample Output 1

1

If Takahashi directly transmits the information to Town 2 and 4, Town 1, 2, 3, 4, 5 receives it at time 1, 0, 1, 0, 1, respectively. In this case, the information is spread all over the kingdom at time 1. We can prove that this is the earliest possible time.

Sample Input 2

5 1
1 2
1 3
1 4
5 4

Sample Output 2

2

Sample Input 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

Sample Output 3

3