Інтервали на дереві#10667
Задано дерево з вершинами і n - 1 ребром, пронумерованими відповідно як 1, 2, \ldots, n і 1, 2, \ldots, n - 1. Ребро з'єднує вершини u_i і v_i.
Для чисел , (1 \le L \le R \le n) визначимо функцію f(L, R) наступним чином:
Нехай - множина вершин з номерами від до . Функція f(L, R) представляє кількість компонент зв'язності в підграфі, утвореному тільки з множини вершин і ребер, обидва кінці яких належать .
Обчисліть
Перший рядок містить число (1 \le n \le 2 \cdot 10^5). Кожен з наступних n - 1 рядків містить дві вершини (u_i, v_i) (1 \le u_i, v_i \le n) - ребро в графі.
Виведіть значення суми.
Приклад 1
Існує шість можливих пар (, ):
Для L = 1, R = 1, S = \{1\}, є зв'язна компонента.
Для L = 1, R = 2, S = \{1, 2\}, є зв'язні компоненти.
Для L = 1, R = 3, S = \{1, 2, 3\}, є зв'язна компонента, оскільки містить обидва кінці кожного з ребер , .
Для L = 2, R = 2, S = \{2\}, є зв'язна компонента.
Для L = 2, R = 3, S = \{2, 3\}, є зв'язна компонента, оскільки містить обидва кінці ребра .
Для L = 3, R = 3, S = \{3\}, є зв'язна компонента.
Сума всіх значень дорівнює .