No.872 All Tree Path
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 174
作問者 :
ningenMe
/ テスター :
onakaT_Titai
タグ : / 解いたユーザー数 174
作問者 :
ningenMe
/ テスター :
onakaT_Titai
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。