CF1458F.Range Diameter Sum

You are given a tree with $n$ vertices numbered $1, \ldots, n$. A tree is a connected simple graph without cycles.

Let $\mathrm{dist}(u, v)$ be the number of edges in the unique simple path connecting vertices $u$ and $v$.

Let $\mathrm{diam}(l, r) = \max \mathrm{dist}(u, v)$ over all pairs $u, v$ such that $l \leq u, v \leq r$.

Compute $\sum_{1 \leq l \leq r \leq n} \mathrm{diam}(l, r)$.

给你一棵包含 $n$ 个顶点的树，顶点编号为 $1, \ldots, n$。树是一种无环的连通简单图。

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

令 $\mathrm{diam}(l, r) = \max \mathrm{dist}(u, v)$，其中最大值取遍所有满足 $l \leq u, v \leq r$ 的顶点对 $(u, v)$。

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

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of vertices in the tree.

The next $n - 1$ lines describe the tree edges. Each of these lines contains two integers $u, v$ ($1 \leq u, v \leq n$) — endpoint indices of the respective tree edge. It is guaranteed that the edge list indeed describes a tree.

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

接下来的 $n - 1$ 行描述树的边。每行包含两个整数 $u, v$（$1 \leq u, v \leq n$）——对应树边的两个端点编号。保证所给边列表确实构成一棵树。

Print a single integer — $\sum_{1 \leq l \leq r \leq n} \mathrm{diam}(l, r)$.

输出一个整数——$\sum_{1 \leq l \leq r \leq n} \mathrm{diam}(l, r)$。