問題一覧 > 通常問題

No.872 All Tree Path

レベル : / AI推定難易度 : 1250 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 181
作問者 : ningenMe / テスター : onakaT_Titai
お気に入りにしたユーザー ProblemId : 3128 / 自分の提出
問題文最終更新日: 2019-08-30 01:10:00
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
yukicoder contest 221 (順位表) の他の問題:

Problem Statement

There is a tree with $N$ vertices. The $i \ (1 \le i \le N-1)$-th edge of this tree bidirectionally connects vertex $u_i$ and vertex $v_i$, and its length is $w_i$.
Let $d_{s,t}$ be the shortest distance between vertex $s$ and vertex $t$. Find $\sum _{s=1} ^{N} {\sum _{t=1} ^{N} {d_{s,t}}}$. Here, $d_{i,i}=0 \ (1 \le i \le N)$.

Input

$N$
$u_{1}\ v_{1}\ w_{1}$
$u_{2}\ v_{2}\ w_{2}$
$\vdots$
$u_{N-1}\ v_{N-1}\ w_{N-1}$

$2 \le N \le 2×10^5$
$1 \le u_i,v_i \le N \ (1 \le i \le N-1)$
$1 \le w_i \le 100 \ (1 \le i \le N-1)$
The given graph is a tree.

Output

Output the answer on one line. Print a newline at the end.

Sample

Sample 1
Input
3
1 2 1
2 3 2
Output
12

Since $d_{1,2}=1,d_{1,3}=3,d_{2,1}=1,d_{2,3}=2,d_{3,1}=3,d_{3,2}=2$, the answer is $12$.

Sample 2
Input
5
2 5 2
2 3 10
1 3 8
3 4 7
Output
256

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