Hotel

Hotel

题目描述

有一个树形结构的宾馆,n个房间,n-1条无向边,每条边的长度相同,任意两个房间可以相互到达。吉丽要给他的三个妹子各开(一个)房(间)。三个妹子住的房间要互不相同(否则要打起来了),为了让吉丽满意,你需要让三个房间两两距离相同。
有多少种方案能让吉丽满意?

输入格式

第一行一个数n。
接下来n-1行,每行两个数x,y,表示x和y之间有一条边相连。

输出格式

让吉丽满意的方案数。

样例输入

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

样例输出

5

提示

【样例解释】
{1,3,5},{2,4,6},{2,4,7},{2,6,7},{4,6,7}

【数据范围】
n≤5000
By Dzy

信息

难度
8
分类
(无)
标签
递交数
16
已通过
4
通过率
25%
上传者