分数: 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