在一個城市裡有N間房子,房子與房子之間有道路相連。任何兩棟房子之間都可以經過某些道路互相往來,而在不重複經過某些路段的情形下,這條路線也是唯一的。換句話說,若把房子看成點,道路看成邊,那麼整個圖形成了一棵樹。
編號為1的房子其實是一間郵局。裡面有兩位郵差每天辛苦地遞送信件到這個城市裡所有的房子。由於郵差們相當地辛苦,他們想要規劃遞送郵件的路線,使得每一天每一棟房子至少有一名郵差送信抵達,而且最後一封信被送出的時間越早越好。
已知郵差們送信時,經過每一段道路的時間恰好都是一分鐘,而且投遞信件到房子裡的時間可以忽略。你能夠幫他們找出最佳路線中,最後一封信抵達的時間嗎?假設兩位郵差在第0分鐘這個時刻同時出發的。
輸入可能包含多筆測試資料。每一筆測試資料的第一列有一個正整數N (1<=N<=3000)代表有N間房子。接下來的N-1列每一列有兩個正整數A, B (1<=A, B<=N)代表有一條道路連接A, B這兩間房子,所有的輸入都是合法的,並且輸入以EOF結束。
對於每一筆測試資料,請輸出最佳路線中,最後一封信抵達的時間(以分鐘為單位)。
6 1 2 2 3 5 2 3 4 6 1
4
Migrated from old NTUJ.
POI ONTAK2009 day2 prob2
No. | Testdata Range | Score |
---|