問題一覧 > 通常問題

No.872 All Tree Path

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 133
作問者 : ningenMeningenMe / テスター : onakaT_TitaionakaT_Titai
14 ProblemId : 3128 / 出題時の順位表
問題文最終更新日: 2019-08-30 01:10:00

問題文

$N$頂点の木があります。 この木の$i \ (1 \le i \le N-1)$番目の辺は頂点$u_i$と頂点$v_i$を双方向に結んでいて、その長さは$w_i$です。
頂点$s$と頂点$t$の最短距離を$d_{s,t}$とします。$\sum _{s=1} ^{N} {\sum _{t=1} ^{N} {d_{s,t}}}$を求めてください。なお$d_{i,i}=0 \ (1 \le i \le N)$とします。

入力

$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)$
与えられるグラフは木である。

出力

答えを一行で出力してください。最後に改行してください。

サンプル

サンプル1
入力
3
1 2 1
2 3 2
出力
12

$d_{1,2}=1,d_{1,3}=3,d_{2,1}=1,d_{2,3}=2,d_{3,1}=3,d_{3,2}=2$より答えは$12$です。

サンプル2
入力
5
2 5 2
2 3 10
1 3 8
3 4 7
出力
256

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