Задача про дерево
Обмеження: 2 сек., 256 МіБ
Вам задано дерево з nn вершин, пронумерованих від 1 до nn.
Вам цікаво, скільки існує пар шляхів, які не мають спільної вершини. Формально, потрібно знайти кількість четвірок чисел a,b,ca,b,c та dd, для яких:
1≤a<b≤n1≤a<b≤n;
1≤c<d≤n1≤c<d≤n;
не існує вершини, яка лежить на шляху від aa до bb та від cc до dd.
Знайдіть кількість таких пар шляхів.
Вхідні дані
У першому рядку задано ціле число nn — кількість вершин дерева.
У наступних n−1n−1 рядках задано пари чисел uiui та vivi — ребра дерева.
Вихідні дані
У єдиному рядку виведіть ціле число — відповідь на задачу.
Обмеження
1≤n≤8⋅1041≤n≤8⋅104,
1≤ui,vi≤n1≤ui,vi≤n,
ui≠viui≠vi.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 4 1 2 2 3 3 4 | 2 |