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

输入 #1

3
1 3
2 3

输出 #1

7

输入输出样例 #2

输入 #2

2
1 2

输出 #2

3

输入输出样例 #3

输入 #3

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

输出 #3

113

说明/提示

限制条件

• $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 翻译