TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3795
  • 题目
  • P3795死亡颂唱者
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 1000ms
    问题描述

     老王沉迷于lol不能自拔,召唤师峡谷是一个树状结构,总共有n个节点(3<=n<=1000),其中每条边的长度均为1,红方英雄全部在叶子节点处,每个叶子节点处都有一个红方英雄。可惜的是蓝方英雄死亡颂唱者经济太过领先,一个大招可以秒掉红方英雄。死亡颂唱者的大招是,在颂唱k秒后(1<=k<=n),对所有敌方英雄造成魔法伤害。前面说了,死亡颂唱者发育的非常好,大招可以秒杀红方英雄。但是红方为了不损失人头,决定在峡谷中一些节点处建造一些温泉使得所有英雄都是安全的。已有的一个基地温泉s(1<=s<=n),死亡颂唱者颂唱k秒,即红方英雄在k秒内到达任意一个温泉即是安全的,英雄的移动速度是1个单位每秒。

    输入格式

    第一个数t为数据的组数。对于每一组数据,前三个数分别为n,s,k。后面n-1行,每行2个数a,b。即a,b之间有一条边。

    输出格式

    对于每组数据,输出一行,即最少需要修建的温泉数。

    样例输入


    14
    12 2
    1 2
    2 3
    3 4
    4 5
    5 6
    7 5
    8 5
    4 9
    10 3
    2 12
    12 14
    13 14
    14 11

    样例输出

    1

    提示

    3<=n<=1000

    1<=k,s<=n


    来源  老王 老张 老毛