Finding pairs#11609
A tree with vertices is given. Vertex is considered the root. There is exactly one simple path between any two vertices.
Let d(i, j) denote the number of edges on the path from vertex to vertex .
Find the number of vertex pairs such that the following equality holds:
The first line contains a single integer n~(1 \le n \le 10^5) — the number of vertices in the tree.
Each of the next n-1 lines contains two integers, describing the edges of the tree: the pairs of vertices connected by an edge.
Print a single integer — the number of pairs for which d(i, j) = d(i, 1) - d(j, 1) holds.
Example 1