树上的区间

题目描述

有一棵由 $N$ 个顶点和 $N-1$ 条边组成的树,顶点编号为 $1, 2,\cdots, N$,边编号为 $1, 2, \cdots, N-1$。边 $i$ 连接顶点 $u_i, v_i$。

对于整数 $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)$。

输入格式

输入按以下格式从标准输入给出:

$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)$。

样例

3
1 3
2 3

7

可能的 $L, R$ 组合有以下 $6$ 种:

• 当 $L = 1, R = 1$ 时,$S = \{1\}$,连通分量个数为 $1$。
• 当 $L = 1, R = 2$ 时,$S = \{1, 2\}$,连通分量个数为 $2$。
• 当 $L = 1, R = 3$ 时,$S = \{1, 2, 3\}$,边 $1, 2$ 的两端都属于 $S$,连通分量个数为 $1$。
• 当 $L = 2, R = 2$ 时,$S = \{2\}$,连通分量个数为 $1$。
• 当 $L = 2, R = 3$ 时,$S = \{2, 3\}$,边 $2$ 的两端都属于 $S$,连通分量个数为 $1$。
• 当 $L = 3, R = 3$ 时,$S = \{3\}$,连通分量个数为 $1$。

它们的和为 $7$。

2
1 2

3

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

113

数据范围

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