← 返回题目列表

Codeforces · 1458/F

F. 范围直径总和

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

给你一棵树,其中 $$$n$$$ 个顶点编号为 $$$1、\ldots、n$$$。树是一个没有环的连接的简单图。

令 $$$\mathrm{dist}(u, v)$$$ 为连接顶点 $$$u$$$ 和 $$$v$$$ 的唯一简单路径中的边数。

设 $$$\mathrm{diam}(l, r) = \max \mathrm{dist}(u, v)$$$ 在所有对 $$$u, v$$$ 上,使得 $$$l \leq u, v \leq r$$$。

计算 $$$\sum_{1 \leq l \leq r \leq n} \mathrm{diam}(l, r)$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 树中的顶点数。

接下来的 $$$n - 1$$$ 行描述树的边缘。每行都包含两个整数 $$$u, v$$$ ($$$1 \leq u, v \leq n$$$) - 相应树边的端点索引。保证边列表确实描述了一棵树。

输出

打印单个整数 - $$$\sum_{1 \leq l \leq r \leq n} \mathrm{diam}(l, r)$$$。

示例

输入 #1

4
1 2
2 4
3 2

输出 #1

10

输入 #2

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

输出 #2

224