099 - Tree Distance(★5)
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点:5 点
問題文
N 頂点の木が与えられます。木の頂点にはそれぞれ 1 から N までの番号が振られています。
i 番目の辺は、頂点 a_i と頂点 b_i を双方向に結んでおり、長さは全て 1 です。
- {\displaystyle\sum_{u = 1}^{N - 1} \sum_{v = u + 1}^{N} \operatorname{dist}(u, v)}
の値を求めてください。
ただし、\operatorname{dist}(u,v) は、頂点 u から 頂点 v までの最短距離とします。
制約
- 2 \leq N \leq 100000
- 1 \leq a_i, b_i \leq N
- 与えられるグラフは木である
- 入力は全て整数で与えられる
入力
入力は以下の形式で標準入力から与えられます。
N a_1 b_1 a_2 b_2 : a_{N - 1} b_{N - 1}
出力
答えを 1 行に出力してください。
入力例 1
2 1 2
出力例 1
1
\operatorname{dist}(1, 2) = 1 であるので、答えは 1 です。
入力例 2
4 1 2 1 3 1 4
出力例 2
9
- \operatorname{dist}(1, 2) = 1
- \operatorname{dist}(1, 3) = 1
- \operatorname{dist}(1, 4) = 1
- \operatorname{dist}(2, 3) = 2
- \operatorname{dist}(2, 4) = 2
- \operatorname{dist}(3, 4) = 2
であるので、これらを足し合わせた 9 が答えになります。
入力例 3
12 1 2 3 1 4 2 2 5 3 6 3 7 8 4 4 9 10 5 11 7 7 12
出力例 3
211