e-olymp
Змагання

July 9 - ADA Training

Интервалы на дереве

Задано дерево из n вершин и n1 ребер, соответственно пронумерованных 1, 2, ..., n и 1, 2, ..., n1. Ребро i соединяет вершины ui и vi.

Для чисел L, R (1LRn) объявим функцию f(L, R) следующим образом:

  • Пусть S - множество вершин с номерами от L до R. Функция f (L, R) представляет собой количество компонент связности в подграфе, образованном только из множества вершин S и ребер, оба конца которых принадлежат S.

Вычислите prb10667.gif

Входные данные

Первая строка содержит число n (1n2 * 105). Каждая из следующих n - 1 строк содержит две вершины (ui, vi) (1ui, vin) - ребро в графе.

Выходные данные

Выведите значение суммы.

Пример

Имеются шесть возможных пар (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.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3
1 3
2 3
Вихідні дані #1
7