No.872 All Tree Path

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 92
作問者 : ningenMeningenMe / テスター : onakaT_TitaionakaT_Titai
10 ProblemId : 3128 / 出題時の順位表

問題文

$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

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。