AT_arc116_e [ARC116E] Spread of Information

[problemUrl]: https://atcoder.jp/contests/arc116/tasks/arc116_e 高橋国には $ 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/A

N/A

### 制約 - 入力は全て整数 - $ 1\ \leq\ K\