No.872 All Tree Path
タグ : / 解いたユーザー数 181
作問者 :
onakaT_Titai
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もしくは右上の雲マークをクリックしてアカウントを作成してください。