树的直径(distance)

题目描述

给定一棵有 $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)$。

输入格式

从 distance.in 输入数据。

第一行包含一个整数 $n$，表示树的顶点数。

接下来的 $n-1$ 行，每行包含两个整数 $u, v$，表示树中的一条边。

输出格式

输出数据到 distance.out 里。

输出一个整数，表示答案。

【样例 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

【样例 3】

见选手目录下的 distance/distance3.in 和 distance/distance3.ans。

该样例满足测试点 $3$ 的约束。

【样例 4】

见选手目录下的 distance/distance3.in 和 distance/distance3.ans。

该样例满足测试点 $5$ 的约束。

【样例 5】

见选手目录下的 distance/distance3.in 和 distance/distance3.ans。

该样例满足测试点 $8$ 的约束。

【数据范围】

对于 $100$ 的数据，满足 $1 \le n \le 10^6$，输入的边构成一棵树。