飞机票： http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16451

题意：就是给你一棵树，给你一个服务器，求在其余非叶子节点上放服务器，使任意的叶子节点到最近服务器的距离不超过k

分析：可以根据树形的性质来进行解决

具体步骤：用pair来存数据，如果first是1就是说有叶子节点没有服务器，如果first是2就说有服务器在；所以当我们搜到叶子节点的时候，返回(1,1),当搜到父子节点，我们对返回的子节点进行贪心选择，如果是1就选择距离最大的没有服务器的叶子节点，如果是2就选择最近的服务器，如果1+2的距离（1，为叶子节点最远距离，2为服务器最近距离）<=k那么就是可以访问到，则返回2，且服务器的距离要加1；如果>k那么就是说访问不到，那么我们要判断，如果1==k则必须架服务器了，不加则不满足条件，如果<k则返回叶子节点距离加1.一直递归到s节点，且s节点本身的2为0。。。ok复杂度为O（n-1)即边的数量；

啪啪啪。就可以AC了

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=1234;
vector<int> V[maxn];
int n,T,s,k;
void init()
{
    scanf("%d%d%d",&n,&s,&k);
    for(int i=1; i<=n; i++)V[i].clear();
    int u,v;
    for(int i=1; i<n; i++)
    {
        scanf("%d%d",&u,&v);
        V[u].push_back(v);
        V[v].push_back(u);
    }
}
int MIN;
pair<int,int> DFS(int now,int fa)
{
    int a1=-1;
    int a2=-1;
    if(now==s)a2=0;
    for(int i=0; i<V[now].size(); i++)
    {
        int v=V[now][i];
        if(v==fa)continue;
        pair<int,int> p= DFS(v,now);
        if(p.first==1)
        {
            a1=max(a1,p.second);
        }
        else
        {
            if(a2==-1)a2=p.second;
            else
                a2=min(a2,p.second);
        }
    }
    if(a1==-1&&a2==-1)
    {
        return make_pair(1,1);
    }
    if(a1!=-1&&a2!=-1)
    {
        if(a1+a2<=k)
        {
            return make_pair(2,a2+1);
        }
        else
        {
            if(a1==k)
            {
                MIN++;
                return make_pair(2,1);
            }
            return make_pair(1,a1+1);
        }
    }
    if(a1==-1)
    {
        return make_pair(2,a2+1);
    }
    if(a1==k)
    {
        MIN++;
        return make_pair(2,1);
    }
    return make_pair(1,a1+1);
}
void play()
{
    MIN=0;
    DFS(s,0);
    printf("%d\n",MIN);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    return 0;
}