750 . 最大的壯遊

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

77.3% (17/22)

Tags

apcsc apcsc-dc

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

Sample Output 2

100

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~20 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 2
1 3000 524288 65536 1 2
2 3000 524288 65536 2
3 3000 524288 65536 2
4 3000 524288 65536 2
5 3000 524288 65536 2
6 3000 524288 65536 2
7 3000 524288 65536 2
8 3000 524288 65536 2
9 3000 524288 65536 2
10 3000 524288 65536 2
11 3000 524288 65536 2
12 3000 524288 65536 2
13 3000 524288 65536 2
14 3000 524288 65536 2
15 3000 524288 65536 2
16 3000 524288 65536 2
17 3000 524288 65536 2
18 3000 524288 65536 2
19 3000 524288 65536 2
20 3000 524288 65536 2
Submit
Back to Top