中文
日本語
English
| P3867旅馆 | ||
|
问题描述
何老板开了一间宾馆，共n个房间，通过n-1双向道路相连，每条道路的长度相同，任意两个房间都有且仅有一条路径可以到达。有三名同行的顾客需要各开一个房间。三个客人要求住的房间要互不相同，且三个房间两两距离相同。
何老板想知道，有多少种方案能让他们满意？
输入格式
第一行一个数n。
接下来n-1行，每行两个数x,y，表示x和y之间有一条道路相连。
输出格式
一个整数，表示满足要求的方案数。
样例输入 1
7
1 2
5 7
2 5
2 3
5 6
4 5
样例输出 1
5
样例输入 2
20
1 2
2 3
1 4
3 5
2 6
4 7
6 8
4 9
7 10
10 11
9 12
3 13
9 14
5 15
2 16
6 17
5 18
11 19
4 20
样例输出 2
18
提示
【样例1说明】
{1,3,5},{2,4,6},{2,4,7},{2,6,7},{4,6,7}
【数据范围】
对于30%的数据 1≤N≤100
对于50%的数据 1≤N≤5000