F. Сумма диаметров
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево с $$$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