给定一棵包含 N个顶点的树。顶点编号为 1 至 N，第 i条边 (1≤i≤N−1) 连接顶点 ai与顶点 bi。

对于树中任意两个顶点 u 和 v（满足 u<v），定义距离 d(u,v)为连接 u 和 v的简单路径上的边的数量。

请计算所有满足 u<v的顶点对 (u,v) 的距离 d(u,v) 的总和。

输入格式

第一行 ，一个整数表示n

接下来的n−1行，每行两个整数a_i,b_i.

输出格式

输出所有满足 u<v的顶点对 (u,v) 的距离 d(u,v)的总和。

输入样例#1

3
1 2
2 3

输出样例#1

3

输入样例#2

5
1 2
1 3
1 4
1 5

输出样例#2

10

说明提示

【 数据范围 】

2≤N≤10⁵

1≤a_i,b_i≤N

限制

时间限制：1000ms

内存限制：256MiB

首先，我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）遍历树的每个节点。对于每个节点，我们可以计算从根节点到该节点的距离，并将这个距离乘以节点数。通过这种方式，我们可以计算所有顶点对的距离总和。具体实现时，我们可以使用一个数组来存储每个节点的距离值，并在遍历过程中累加距离值。最后，将所有累加的距离值相加即可得到结果。时间复杂度为O(N)。

题目要求计算树中所有顶点对之间的距离总和。我们可以使用深度优先搜索或广度优先搜索来遍历树的每个节点。对于每个节点，我们可以计算从根节点到该节点的距离，并将这个距离乘以节点数。这是因为对于每个节点u，其与所有其他节点v的距离总和等于从根节点到节点u的距离乘以树中剩余的节点数（即总节点数减去u的子孙节点数）。因此，我们可以使用一个数组来存储每个节点的距离值，并在遍历过程中累加距离值。最后将所有累加的距离值相加即可得到结果。具体实现时需要注意细节问题，如初始化数组等。时间复杂度为O(N)。