题目描述

我们有一棵包含$N$个顶点和$N-1$条边的树，分别编号为$1, 2,\\cdots, N$和$1, 2, \\cdots, N-1$。边$i$连接了顶点$u_i$和$v_i$。

对于整数$L, R$（$1 \leq L \leq R \leq N$），我们定义函数$f(L, R)$如下：

• 设$S$是由编号从$L$到$R$的顶点组成的集合。$f(L, R)$表示仅由顶点集合$S$和其两端点均属于$S$的边构成的子图中连通分量的数量。

计算$\\sum_{L=1}^{N} \\sum_{R=L}^{N} f(L, R)$。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N$
• 给定的图是一棵树。
• 输入中的所有值均为整数。

输入

输入以以下格式从标准输入给出：

$N$
$u_1$ $v_1$
$u_2$ $v_2$
:
$u_{N-1}$ $v_{N-1}$

输出

打印$\\sum_{L=1}^{N} \\sum_{R=L}^{N} f(L, R)$。

示例输入1

3
1 3
2 3

示例输出1

7

对于下列六个可能的$(L, R)$，有如下结果：

• 对于$L = 1, R = 1$，$S = \\{1\\}$，我们有$1$个连通分量。
• 对于$L = 1, R = 2$，$S = \\{1, 2\\}$，我们有$2$个连通分量。
• 对于$L = 1, R = 3$，$S = \\{1, 2, 3\\}$，我们有$1$个连通分量，因为$S$包含了边$1, 2$的每个端点。
• 对于$L = 2, R = 2$，$S = \\{2\\}$，我们有$1$个连通分量。
• 对于$L = 2, R = 3$，$S = \\{2, 3\\}$，我们有$1$个连通分量，因为$S$包含了边$2$的两个端点。
• 对于$L = 3, R = 3$，$S = \\{3\\}$，我们有$1$个连通分量。

这些结果的和为$7$。

示例输入2

2
1 2

示例输出2

3

示例输入3

10
5 3
5 7
8 9
1 9
9 10
8 4
7 4
6 10
7 2

示例输出3

113