AT_abc173_f [ABC173F] Intervals on Tree

有一棵包含 $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$ > $\vdots$ > $u_{N-1}$ $v_{N-1}$

输出 $\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$ - 给定的图一定是一棵树 - 输入均为整数 ## 样例解释 1 所有可能的 $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$。 由 ChatGPT 4.1 翻译