750 . 最大的壯遊
TopCoder
Description
河豚國是一個由互相聯通的 $n$ 個點和 $n - 1$ 條邊所組成的無向圖。
小 P 最近想要體驗壯遊，他希望能在河豚國找出最長的一條路徑。
也就是從某個點出發，不重複的經過一些點直到另一個點（可以是起點），經過的邊長度總和盡量大。
注意邊長度有可能是負的。
Input Format
一行包含一個正整數 $n$。
接下來有 $n-1$ 行，每行包含兩個數字 $a$, $b$, $c$。
代表編號為 $a$ 的城市與編號為 $b$ 的城市中間有一條長度為 $c$ 的道路。
- $n \le 10^ 6$
- $1 \le a,b \le n$
- $|c| \le 10^ 9$
Output Format
請輸出一個數字代表最大的「經過的邊長度總和」
Sample Input 1
1
Sample Output 1
0
Sample Input 2
2
1 2 100
1 2 100
Sample Output 2
100
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~20 | 無額外限制 | 100 |