Distance to LCA
Limits: 2 sec., 256 MiB
This statement was translated automatically from Ukrainian.
Zenyk and Marichka have a rooted undirected tree with \(n\) vertices. All vertices are numbered with integers from 1 to \(n\) inclusive, and the vertex with number 1 is the root of the tree.
They want to choose a pair of distinct vertices \(a, b\). After that, they find the lowest common ancestor of these vertices — a vertex \(c\) that simultaneously lies on the simple path from the root to \(a\) and on the simple path from the root to \(b\), and is the farthest from the root. Then they find two numbers: \(dist(a, c)\) and \(dist(b, c)\) — the distance (number of edges) on the simple path between the corresponding vertices.
Your task is to find the sum of \(dist(a, c) \cdot dist(b, c)\) over all possible pairs \(a, b\) (\(1 \le a < b \le n\)).
Input
The first line contains a single integer \(n\) — the number of vertices in the tree.
The next \(n-1\) lines contain pairs of numbers \(u_i\) and \(v_i\), separated by spaces — the edges of the tree.
Output
Output a single integer — the answer to the problem.
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 |
|---|