配点: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