Інтервали на дереві
Задано дерево з 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.