TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  训练指南  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5032
  • 题目
  • P5032死亡的颂唱者
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,128m
    问题描述

    老王沉迷于 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 之间有一条边。

    输出格式

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

    样例输入 1


    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

    1

    样例输入 2


    7 4 1 
    4 6 
    3 4 
    4 2 
    2 7 
    4 5 
    5 1 
    10 4 2 
    4 7 
    4 9 
    9 5 
    5 10 
    3 9 
    8 10 
    6 8 
    1 4 
    7 2

    样例输出 2

    2
    1

    提示

    对于 40%的数据,3<=n<=50
    对于 100%的数据,3<=n<=1000 1<=k,s<=n 1<=t<=10