TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  課程の中心  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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