P5904 [POI 2014] HOT-Hotels Enhanced Version

Same as [[POI2014]HOT-Hotels](https://www.luogu.com.cn/problem/P3565), but the Constraints are increased to $1 \le n \le 10^5$. Source: BZOJ4543.

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.

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 one integer in one line, representing the number of all valid triples of nodes.

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