← 返回题目列表

AtCoder · abc438_f

F. 墨西哥总和

中文机器翻译题面 查看原题

分数: 525 点

问题陈述

你得到一棵树 T 与 N 顶点。顶点编号从 0 to N-1,以及 i第边缘 (1\le i\le N-1) 双向连接顶点 u_i 和 v_i。 (请注意,顶点编号为 0 索引,边编号为 1 索引。)

对于一对整数 (i,j) 其中 0 \leq i,j < N,定义 f(i,j) 如下:

  • 顶点中编号最小的顶点的顶点编号 不包括在内 在从顶点开始的路径中 i 到顶点 j 在树中 T.
    • 这里,如果从顶点开始的路径 i 到顶点 j 包括顶点中的所有顶点 0 到顶点 N-1,让 f(i,j)=N.

请注意,从顶点开始的路径 i 到顶点 j 在树中 T 包括顶点 i 和 j.

查找值 \displaystyle \sum_{0\le i \le j < N} f(i,j).

约束

  • 2\le N\le 2\times 10^5
  • 0\le u_i < v_i < N
  • 输入中给出的图是一棵树。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

输出

输出值 \displaystyle \sum_{0\le i \le j < N} f(i,j).


示例输入 1

2
0 1

示例输出 1

3

我们有 f(0,0)=1,f(0,1)=2,f(1,1)=0。因此,输出 1+2+0=3.


示例输入 2

5
0 1
0 2
2 3
2 4

示例输出 2

16

示例输入 3

7
1 4
2 6
0 5
0 3
2 5
1 5

示例输出 3

16