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

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