P3565 [POI 2014] HOT-Hotels

在 Byteotia 有 $n$ 个城镇，通过 $n-1$ 条道路连接。 每条道路直接连接两个城镇。 所有的道路长度相同，并且是双向的。 已知每个城镇都可以通过一条或多条（直接连接的）道路到达其他城镇。 换句话说，道路网络形成了一棵树。 Byteotia 的国王 Byteasar 希望建造三家豪华酒店，以吸引来自世界各地的游客。 国王希望这些酒店位于不同的城镇，并且彼此之间的距离相同。 请通过编写程序来帮助国王，确定在 Byteotia 中可能的酒店三元组位置的数量。

标准输入的第一行包含一个整数 $n$ ($1\le n\le 5\ 000$)，表示 Byteotia 中的城镇数量。 城镇编号从 $1$ 到 $n$。 接下来 $n-1$ 行描述了 Byteotia 的道路网络。 每行包含两个整数 $a$ 和 $b$ ($1\le a\le b\le n$)，用一个空格分隔，表示在城镇 $a$ 和 $b$ 之间有一条直接的道路。

标准输出的第一行应包含一个整数，表示可能的酒店位置的数量。

题面翻译由 ChatGPT-4o 提供。