TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2287
  • 题目
  • P2287【博弈】砍树游戏
    限制 : 时间限制 : 10000 MS   空间限制 : 165536 KB
    问题描述

    tclsm、littleSheep两人在玩一种有趣的游戏。该游戏的地图是一棵树,树上共N个节点,编号0到N-1,0号节点为树的根,树上共有N-1条边。玩家们轮流出招。A首先出招,每次出招分两步:第一步,玩家选择一条边,并把它砍断;第二步,玩家把不能连接到根的所有边都删除。无边可删的玩家算输。
    A玩了几局后表示上述游戏过于简单,他想要增加游戏难度,于是他提出问题:假如树中每条边要被砍K次才能被砍断,谁赢谁输?
    假设A和B都非常聪明,从不会失误。

    输入格式

    第一行,一个整数N (1<=N<=10^6),表示节点总数
    接下来N-1行,每行两个整数 I , J(0<=I, J<N), 表示节点I和节点J有条边直接相连。
    接下来一个整数Q (1<=Q<=10^6), 表示总的询问数。
    接下来Q行,每行一个整数K(1<=K<=10^4),表示要切K砍才能切断一条边。

    输出格式

    对于每个询问,输出赢家的名字。

    样例输入

    【样例输入1】
    3
    1 0
    1 2
    2
    1
    2
    【样例输入2】
    3
    0 1
    0 2
    1
    1

    样例输出

    【样例输出1】
    tclsm
    littleSheep
    【样例输出2】
    littleSheep

    提示

    100% n<=10^6 k<=10^4 q<=n