CF1458F Range Diameter Sum

Description

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

Input Format

N/A

Output Format

N/A