Вам дано дерево с \(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)\).
Выходные данные
Выведите одно целое число — \(\sum_{1 \leq l \leq r \leq n} \mathrm{diam}(l, r)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2
2 4
3 2
|
10
|
|
2
|
10
1 8
2 9
5 6
4 8
4 2
7 9
3 6
10 4
3 9
|
224
|