TopCoder

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

User's AC Ratio

100.0% (58/58)

Submission's AC Ratio

60.3% (79/131)

Description

給你一棵加權的無向樹,請問最遠的兩個點距離為何?

Input Format

輸入檔可能包含多筆測試資料,每筆測試資料的第一列有一個正整數n(1<=n<=100,000)代表樹的節點數。
接下來有n-1列,每列有三個數字i,j,c(1<=i,j<=n;1<=c<=1,000)代表樹的一條邊,i,j是連接的兩個節點編號,c是權重。
當n=0時代表輸入結束。

Output Format

對於每筆測試資料請輸出最遠的兩個節點之距離。

Sample Input

5
1 2 8
2 3 7
2 4 6
4 5 2
0

Sample Output

16

Hints

Problem Source

原TIOJ1213 / TIOJ 2008例行賽03 (prob E)。經典問題練習。Problem Setter:Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 65536