Интервалы на дереве
Интервалы на дереве
Задано дерево из n вершин и n − 1 ребер, соответственно пронумерованных 1, 2, ..., n и 1, 2, ..., n − 1. Ребро i соединяет вершины ui
и vi
.
Для чисел L, R (1 ≤ L ≤ R ≤ n) объявим функцию f(L, R) следующим образом:
- Пусть S - множество вершин с номерами от L до R. Функция f (L, R) представляет собой количество компонент связности в подграфе, образованном только из множества вершин S и ребер, оба конца которых принадлежат S.
Вычислите
Входные данные
Первая строка содержит число n (1 ≤ n ≤ 2 * 105
). Каждая из следующих n - 1 строк содержит две вершины (ui
, vi
) (1 ≤ ui
, vi
≤ n) - ребро в графе.
Выходные данные
Выведите значение суммы.
Пример
Имеются шесть возможных пар (L, R):
Для L = 1, R = 1, S = {1}, имеется 1 связная компонента.
Для L = 1, R = 2, S = {1, 2}, имеется 2 связные компоненты.
Для L = 1, R = 3, S = {1, 2, 3}, имеется 1 связная компонента, так как S содержит оба конца каждого из ребер 1, 2.
Для L = 2, R = 2, S = {2}, имеется 1 связная компонента.
Для L = 2, R = 3, S = {2, 3}, имеется 1 связная компонента, так как S содержит оба конца ребра 2.
Для L = 3, R = 3, S = {3}, имеется 1 связная компонента.
Сумма всех значений равна 7.
3 1 3 2 3
7