TopCoder

User's AC Ratio

97.1% (102/105)

Submission's AC Ratio

52.8% (141/267)

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

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1