题目大意：
在非叶子节点上安装最少的服务器使得，每个叶子节点到服务器的距离不超过k。
贪心+图上的dfs。 先从深度最大的叶子节点开始找。找到父节点后再用这个父节点进行扩充。
/* *********************************************** Author :guanjun Created Time :2016/5/10 23:15:38 File Name :7.cpp ************************************************ */ #include <iostream> #include <cstring> #include <cstdlib> #include <stdio.h> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <iomanip> #include <list> #include <deque> #include <stack> #define ull unsigned long long #define ll long long #define mod 90001 #define INF 0x3f3f3f3f #define maxn 10010 #define cle(a) memset(a,0,sizeof(a)) const ull inf = 1LL << 61; const double eps=1e-5; using namespace std; int n,s,k; vector<int>gr[maxn]; vector<int>nod[maxn]; int fa[maxn]; int vis[maxn]; void dfs(int f,int u,int d){ fa[u]=f; int x=gr[u].size(); if(x==1&&d>k)nod[d].push_back(u); for(int i=0;i<x;i++){ int v=gr[u][i]; if(v!=f)dfs(u,v,d+1); } } void dfs1(int f,int u,int d){ vis[u]=1; int x=gr[u].size(); for(int i=0;i<x;i++){ int v=gr[u][i]; if(v!=f&&d<k)dfs1(u,v,d+1); } } int solve(){ int ans=0; cle(vis); for(int d=n-1;d>k;d--){ for(int j=0;j<nod[d].size();j++){ int u=nod[d][j]; if(vis[u])continue; int v=u; for(int i=0;i<k;i++)v=fa[v]; ans++; dfs1(-1,v,0); } } return ans; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif //freopen("out.txt","w",stdout); int t,a,b; cin>>t; while(t--){ cin>>n>>s>>k; cle(fa); for(int i=0;i<=n;i++)gr[i].clear(),nod[i].clear(); for(int i=1;i<n;i++){ scanf("%d%d",&a,&b); gr[a].push_back(b); gr[b].push_back(a); } dfs(-1,s,0); printf("%d ",solve()); } return 0; }