Интервалы на дереве
Задано дерево из n вершин и n − 1 ребер, соответственно пронумерованных 1, 2, ..., n и 1, 2, ..., n − 1. Ребро i соединяет вершины u[i] и v[i].
Для чисел L, R (1 ≤ L ≤ R ≤ n) объявим функцию f(L, R) следующим образом:
Пусть S - множество вершин с номерами от L до R. Функция f (L, R) представляет собой количество компонент связности в подграфе, образованном только из множества вершин S и ребер, оба конца которых принадлежат S.
Вычислите
Входные данные
Первая строка содержит число n (1 ≤ n ≤ 2 * 10^5). Каждая из следующих n - 1 строк содержит две вершины (u[i], v[i]) (1 ≤ u[i], v[i] ≤ 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.