Range Diameter Sum

题意翻译

给定一棵包含 $n$ 个节点(编号 $1$ 到 $n$), $n-1$ 条长度为 $1$ 的无向边的树. 设 $d(u,v)$ 为编号 $u$ 到编号 $v$ 两点之间唯一路径的长度. 设 $f(l,r)$ 为 $\max\{d(u,v)\}.(l\leq u,v\leq r)$ 求: $$\sum_{l=1}^{n}\sum_{r=l}^{n}f(l,r)$$ 第一行输入 $1$ 个整数 $n(1\leq n\leq 10^5)$. 接下来 $n-1$ 行,每行两个整数 $x,y$ 表示编号为 $x$ 和编号为 $y$ 的点之间有一条长度为 $1$ 的边$(1\leq x,y\leq n)$,保证给定的图是一棵树. 输出对于这棵树,上述表达式的值.

题目描述

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) $ .

输入输出格式

输入格式

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.

输出格式

Print a single integer — $ \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