You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

树上计数

题目描述

给定一棵树，标号从 $1$ 到 $n$，求无序三元组 $(x,y,z)$ 的数量满足 $dist(x,y)=dist(y,z)=dist(x,z)$ 且 $x,y,z$ 互不相等。

其中 $dist(x,y)$ 表示 $x$ 和 $y$ 在树上的距离。

输入格式

第一行一个正整数 $n$，表示点数。

接下去 $n-1$ 行，每行两个正整数 $x,y$，描述了树上的一条边，连接 $x,y$。

输出格式

上述三元组数量。

样例

Input 1

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

Output 1

5

不同的三元组有：

{1,3,5},{2,4,6},{2,4,7},{2,6,7},{4,6,7}

提示说明

对于前 $0\%$ 的数据，是样例。

对于前 $20\%$ 的数据，保证 $n\le 100$。

对于前 $30\%$ 的数据，保证 $n\le 5000$。

对于另外 $30\%$ 的数据，保证 $n\le 10^5$，且数据随机。

对于 $100\%$ 的数据，保证 $n\le 10^5$。