生活在树上

时间限制：1s

空间限制：64MB

题目描述

给定一棵由 \(n\) 个结点组成的树，设\(dis(u,v)\)是两点之间的距离。

求
\[\sum_{1\le i<j\le n}dis(i,j)\]

输入格式

第一行两个正整数\(n\)。

接下来 \(n-1\) 行每行两个整数\(u,v\)，表示树的一条边

输出格式

输出答案。

样例输入1

4
1 2
1 3
1 4

样例输出1

9

样例1解释

\(1\to 2\)的距离为\(1\)

\(1\to 3\)的距离为\(1\)

\(1\to 4\)的距离为\(1\)

\(2\to 3\)的距离为\(2\)

\(2\to 4\)的距离为\(2\)

\(3\to 4\)的距离为\(2\)

样例输入2

5
1 3
2 5
4 1
3 2

样例输出2

20

样例2解释

样例输入3

63
7 5
21 12
41 29
24 12
13 9
2 1
2 57
30 19
7 34
42 2
9 61
43 29
24 8
61 44
4 55
7 3
38 56
41 24
60 19
26 22
19 44
15 12
58 41
17 63
46 43
25 23
58 62
53 6
31 4
1 4
20 23
1 34
25 16
6 19
52 56
33 61
29 48
15 6
57 12
39 13
60 37
47 40
63 38
56 13
11 33
51 42
58 32
36 1
40 23
14 62
38 25
38 54
22 40
50 32
15 10
1 18
56 35
27 30
45 28
59 28
50 45
49 63

样例输出3

16956

数据范围

对于 50 % 的数据，\(2\le n\le 100\)

对于 100 % 的数据，\(2 \le n \le 10^5, 1\le u,v\le n\)

保证给出的是一棵树。

注意，答案可能不能用 \(32\) 位整数表示