Background

Same as [POI2014]HOT-Hotels, but the Constraints are increased to $1 \le n \le 10^5$.

Source: BZOJ4543.

Problem Description

Given a tree with $n$ nodes, find how many triples of nodes $(i,j,k)$ satisfy that the distances between every pair among $i,j,k$ are all equal.

$(i,j,k)$ and $(i,k,j)$ are considered the same triple.

Input Format

The first line contains an integer $n$.

The next $n-1$ lines each contain two integers $a,b$, meaning there is an edge between $a$ and $b$.

Output Format

Output one integer in one line, representing the number of all valid triples of nodes.

7
1 2
5 7
2 5
2 3
5 6
4 5

5

Hint

For $100\%$ of the testdata, $1 \le n \le 10^5, 1 \le a \le b \le n$.

Translated by ChatGPT 5