Відстань до LCA
Limits: 2 sec., 256 MiB
Зеник і Марічка мають кореневе неорієнтоване дерево із \(n\) вершин. Усі вершини пронумеровані цілими числами від 1 до \(n\), включно, а вершина з номером 1 є коренем дерева.
Вони хочуть вибрати пару різних вершин \(a, b\). Після цього вони знаходять найнижчого спільного предка цих вершин — таку вершину \(c\), яка одночасно лежить на простому шляху від кореня до \(a\) та на простому шляху від кореня до \(b\), і є найдальшою від кореня. Далі вони знаходять два числа: \(dist(a, c)\) та \(dist(b, c)\) — відстань (кількість ребер) на простому шляху між відповідними вершинами.
Ваше завдання — знайти суму \(dist(a, c) \cdot dist(b, c)\) по всіх можливих парах \(a, b\) (\(1 \le a < b \le n\)).
Input
У першому рядку задано одне ціле число \(n\) — кількість вершин дерева.
У наступних \(n-1\) рядках задано пари чисел \(u_i\) та \(v_i\), розділені пробілами — ребра дерева.
Output
Виведіть одне ціле число — відповідь на задачу.
Constraints
\(1 \le n \le 10^5\),
\(1 \le u_i, v_i \le n\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 1 2 2 3 1 4 | 3 |
| Input (stdin) | Output (stdout) |
|---|---|
| 7 1 2 4 2 2 5 1 3 2 7 7 6 | 17 |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|