TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3867
  • 题目
  • P3867宾馆
    限制 : 时间限制 : - MS   空间限制 : 125536 KB
    评测说明 : 1s
    问题描述

     何老板开了一间宾馆,共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
    对于100%的数据 1≤N≤5000


    来源  改编自Poi2014 hotel