F - 树上区间

得分：$600$分

问题描述

我们有一个包含$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)$。

3
1 3
2 3

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
1 2

3

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

113