← 返回题目列表

AtCoder · abc173_f

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).


示例输入 1

3
1 3
2 3

示例输出 1

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 包含 Edge 的两个端点 2.
  • 对于 L = 3, R = 3, S = \{3\} 我们有 1 连接的组件。

这些的总和是 7.


示例输入 2

2
1 2

示例输出 2

3

示例输入 3

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

示例输出 3

113