Вам дано дерево с \(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)\).
4 1 2 2 4 3 2
10
10 1 8 2 9 5 6 4 8 4 2 7 9 3 6 10 4 3 9
224
7000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач