Задача про дерево
Обмеження: 2 сек., 256 МіБ
Вам задано дерево з \(n\) вершин, пронумерованих від 1 до \(n\).
Вам цікаво, скільки існує пар шляхів, які не мають спільної вершини. Формально, потрібно знайти кількість четвірок чисел \(a, b, c\) та \(d\), для яких:
\(1 \le a < b \le n\);
\(1 \le c < d \le n\);
не існує вершини, яка лежить на шляху від \(a\) до \(b\) та від \(c\) до \(d\).
Знайдіть кількість таких пар шляхів.
Вхідні дані
У першому рядку задано ціле число \(n\) — кількість вершин дерева.
У наступних \(n-1\) рядках задано пари чисел \(u_i\) та \(v_i\) — ребра дерева.
Вихідні дані
У єдиному рядку виведіть ціле число — відповідь на задачу.
Обмеження
\(1 \le n \le 8 \cdot 10^4\),
\(1 \le u_i, v_i \le n\),
\(u_i \ne v_i\).
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 4 1 2 2 3 3 4 | 2 |
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|