費盡千辛萬苦,小向終於找到了希爾伯特所在的房間。小向二話不說地使用了瞬間移動。然而,在她面前的是間空蕩蕩的房間。看起來希爾伯特已經被帶走了。
「可惡!要是我的瞬間移動再成熟點就好…要是…我是個成熟的魔法少女…」
眼淚在眼框打轉,不停地責備自己,小向跪坐在地板上,雙手握拳猛槌著地板,哀嘆自己的無力。
正當小向陷入無盡的哀傷時,一張紙條飛到了小向面前。
「希爾伯特我就帶走啦~」這起事件的犯人用輕佻地語句在紙上草草寫下。
雖然不知道犯人的意圖為何,不過作為某種程度上的彌補,小向想靠一己之力救出希爾伯特。在這之前,他得先找到希爾伯特的位置。
小向緊握著紙條,妄想著她能藉由紙條感應出希爾伯特的所在之處。然而,她什麼也沒感覺到。
「我…不想再那麼沒用了…」小向在心裡祈願。
「我…也想像師父一樣厲害…」
「我…也希望我的魔法能幫助人…」
「我…我…我要成為雙馬尾魔法少女!!!!!」
強大的意念轉化為力量。小向感覺到魔力從身體某處湧現。是錯覺嗎?小向覺得自己正在發光。
管不了那麼多了。小向再次緊握著紙條,帶著強烈的祈願,試圖感應出希爾伯特的位置。
忽然間,大量的資訊衝進小向的腦海中。
「東邊的森林……中心……還有……嗚哇啊!」
一瞬間森林的地圖就有如下載檔案般地瞬間進入了小向的記憶裡。
這片森林有個別名叫作「烏森」。顧名思議這森林黑到了一個不行。不過根據剛剛小向得到的資訊,這森林實際上是棵「樹」,也就是說這個森林由$N$個點以及$N-1$條邊構成,並且任兩點都有一條唯一的簡單路徑連結。而希爾伯特的位置就在這棵樹的「重心」,也就是說將希爾伯特所在的點移除後,剩下的分支中點數的最大值被最小化了。
儘管小向的魔力獲得了一定的提升,但是小向的瞬間移動還是老樣子,必須指定目的地才能移動。因此她還是得先由剛剛得到的資訊中推算出希爾伯特的位置。
第一行有一個正整數$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 |
輸出一個整數,代表移除某個點後餘下的分支中點數的最大值的最小值。
小向找出希爾伯特的位置後馬上使用瞬間移動。然而到了目的地後,小向什麼也沒看見。正當小向覺得奇怪的時候……
「可不能讓你輕易通過呢…」
Problem Set / Description by Paupière
No. | Testdata Range | Score |
---|---|---|
1 | 0~4 | 24 |
2 | 5~9 | 36 |
3 | 10~14 | 40 |