← 返回题目列表

AtCoder · typical90_am

039. 树距(★5)

中文机器翻译题面 查看原题

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