Intervals on Tree

题目描述

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

输入格式

输入从标准输入按以下格式给出： $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

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$ 给定的图是树。 输入中的所有值均为整数。共有六种可能的 $(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$。

标签: AtCoder|abc173F

来源

AtCoder|abc173F