TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

90.9% (20/22)

Submission's AC Ratio

61.4% (35/57)

Tags

Description

費盡千辛萬苦,小向終於找到了希爾伯特所在的房間。小向二話不說地使用了瞬間移動。然而,在她面前的是間空蕩蕩的房間。看起來希爾伯特已經被帶走了。

「可惡!要是我的瞬間移動再成熟點就好…要是…我是個成熟的魔法少女…」

眼淚在眼框打轉,不停地責備自己,小向跪坐在地板上,雙手握拳猛槌著地板,哀嘆自己的無力。

正當小向陷入無盡的哀傷時,一張紙條飛到了小向面前。
「希爾伯特我就帶走啦~」這起事件的犯人用輕佻地語句在紙上草草寫下。

雖然不知道犯人的意圖為何,不過作為某種程度上的彌補,小向想靠一己之力救出希爾伯特。在這之前,他得先找到希爾伯特的位置。
小向緊握著紙條,妄想著她能藉由紙條感應出希爾伯特的所在之處。然而,她什麼也沒感覺到。

「我…不想再那麼沒用了…」小向在心裡祈願。
「我…也想像師父一樣厲害…」
「我…也希望我的魔法能幫助人…」
「我…我…我要成為雙馬尾魔法少女!!!!!」

強大的意念轉化為力量。小向感覺到魔力從身體某處湧現。是錯覺嗎?小向覺得自己正在發光。

管不了那麼多了。小向再次緊握著紙條,帶著強烈的祈願,試圖感應出希爾伯特的位置。
忽然間,大量的資訊衝進小向的腦海中。

「東邊的森林……中心……還有……嗚哇啊!」
一瞬間森林的地圖就有如下載檔案般地瞬間進入了小向的記憶裡。

這片森林有個別名叫作「烏森」。顧名思議這森林黑到了一個不行。不過根據剛剛小向得到的資訊,這森林實際上是棵「樹」,也就是說這個森林由$N$個點以及$N-1$條邊構成,並且任兩點都有一條唯一的簡單路徑連結。而希爾伯特的位置就在這棵樹的「重心」,也就是說將希爾伯特所在的點移除後,剩下的分支中點數的最大值被最小化了。

儘管小向的魔力獲得了一定的提升,但是小向的瞬間移動還是老樣子,必須指定目的地才能移動。因此她還是得先由剛剛得到的資訊中推算出希爾伯特的位置。

Input Format

第一行有一個正整數$N\leq 10^ 6$,代表森林中有幾個點。
接下來有$N-1$行。每行有兩個整數$0\leq a_i,b_i<N$,代表第$a_i$個點和第$b_i$個點之間有一條邊連接。這裡森林中的點編號由0到$N-1$。

子任務(測資) 額外限制 分數
1 (0~4) $N\leq 10^ 4$ 24
2 (5~9) $N\leq 10^ 5$ 36
3 (10~14) 40

Output Format

輸出一個整數,代表移除某個點後餘下的分支中點數的最大值的最小值。

Sample Input

5
0 1
2 1
1 3
3 4

Sample Output

2

Hints

小向找出希爾伯特的位置後馬上使用瞬間移動。然而到了目的地後,小向什麼也沒看見。正當小向覺得奇怪的時候……
「可不能讓你輕易通過呢…」

Problem Source

Problem Set / Description by Paupière

Subtasks

For Testdata: 0 ~ 4, Score: 24
For Testdata: 5 ~ 9, Score: 36
For Testdata: 10 ~ 14, Score: 40
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 262144 65536
1 3000 262144 65536
2 3000 262144 65536
3 3000 262144 65536
4 3000 262144 65536
5 3000 262144 65536
6 3000 262144 65536
7 3000 262144 65536
8 3000 262144 65536
9 3000 262144 65536
10 3000 262144 65536
11 3000 262144 65536
12 3000 262144 65536
13 3000 262144 65536
14 3000 262144 65536