题目描述

译自 POI 2014 Stage 1. 「Hotels」

给定一张图，共有 $n$ 个点，且任意两点间有且仅有一条简单路径将它们连通。每条边的长度相等。

选出三个不同的点，使得三个点之间距离两两相等。求方案数。

输入格式

第一行一个整数 $n$ （$1 \le n \le 5000$），表示节点数。节点以从 $1$ 到 $n$ 的编号表示。

接下来 $n-1$ 行，每行两个整数 $a$ 和 $b$（$1 \le a \lt b \le n$），表示节点 $a$ 与节点 $b$ 之间有一条边直接将它们相连。

输出格式

一行输出一个整数，表示方案数。

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

5

共有 $5$ 种可能的方案：$\{1,3,5\},\{2,4,6\},\{2,4,7\},\{2,6,7\},\{4,6,7\}$

数据范围与提示

对于 $50\%$ 的数据，$n \le 500$ 。
对于 $100\%$ 的数据，$1 \le n \le 5000$ 。