给你一棵树,其中 $$$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