题目背景

同 [POI2014]HOT-Hotels，数据范围加大到 $1 \le n \le 10^5$。

来源于 BZOJ4543。

题目描述

给出一棵有 $n$ 个点的树，求有多少组点 $(i,j,k)$ 满足 $i,j,k$ 两两之间的距离都相等。

$(i,j,k)$ 与 $(i,k,j)$ 算作同一组。

输入格式

第一行一个整数 $n$。

接下来 $n-1$ 行，每行两个整数 $a,b$，表示在 $a,b$ 之间有一条边。

输出格式

一行一个整数，表示所有合法的点的组数。

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

5

提示

对于 $100\%$ 的数据， $1\le n\le10^5, 1\le a\le b\le n$。