TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

95.8% (91/95)

Submission's AC Ratio

63.8% (132/207)

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 1

5
0 1
2 1
1 3
3 4

Sample Output 1

2

Hints

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

Problem Source

Problem Set / Description by Paupière

Subtasks

No. Testdata Range Score
1 0~4 24
2 5~9 36
3 10~14 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 262144 1
1 3000 262144 262144 1
2 3000 262144 262144 1
3 3000 262144 262144 1
4 3000 262144 262144 1
5 3000 262144 262144 2
6 3000 262144 262144 2
7 3000 262144 262144 2
8 3000 262144 262144 2
9 3000 262144 262144 2
10 3000 262144 262144 3
11 3000 262144 262144 3
12 3000 262144 262144 3
13 3000 262144 262144 3
14 3000 262144 262144 3