問題一覧 > 通常問題

No.3113 The farthest point

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 127
作問者 : dayo ZOI / テスター : Naru820 ponjuice kenken714 Nzt3
お気に入りにしたユーザー ProblemId : 12159 / 自分の提出
問題文最終更新日: 2025-04-18 00:29:34
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
CPCTF 2025 : PPC (順位表) の他の問題:

Problem Statement

There is a tree $T$ with $N$ vertices, numbered from $1$ to $N$.
For $1 \leq i \leq N-1$, the $i$-th edge connects vertices $u_i$ and $v_i$ and has weight $w_i$.
Among the simple paths connecting any two vertices of $T$, output the largest value of the sum of the edge weights on the path.

Constraints

  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq u_i, v_i \leq N$
  • $|w_i| \leq 10^9$
  • The given graph is a tree.
  • All input values are integers.

Input

The input is given from standard input in the following format.

$N$
$u_1$ $v_1$ $w_1$
$\vdots$
$u_{N-1}$ $v_{N-1}$ $w_{N-1}$

Output

Output the answer.

Sample

Sample 1
Input
2
1 2 100
Output
100
Sample 2
Input
2
1 2 -100
Output
0
Sample 3
Input
10
1 2 916904626
1 3 372928301
3 4 -110828955
3 5 62817969
6 1 526032989
3 7 799578709
8 3 735091801
9 1 905420374
10 3 1000000000
Output
2289832927

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。