CF1458F Range Diameter Sum

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

由 ChatGPT 4.1 翻译