题目传送门
水蓝题，实际难度绿。

题目分析

本题的难点在于如何确定加上去的服务器的位置。
假定以最初给定的服务器作为根节点。
对于任意两个未覆盖的叶子结点 \(A\)，\(B\)，设 \(A\) 的深度小于 \(B\)，则对于 \(A\)，我们可以往深度较浅或深度较深的方向放置服务器。若将服务器放置在深度较浅的位置，则 \(B\) 一定不能被覆盖，若将服务器放置在深度较深的位置，则 \(B\) 可能会被覆盖。
对于任意一个未覆盖的叶子结点，尽可能地将服务器放得远，即放置在距离该结点距离为 \(k\) 的位置，则服务器能覆盖的期望范围越大。
综上所述，我们得出一个贪心策略：选择深度最深的未覆盖的叶子结点，将服务器放置它的 \(k\) 级祖先处，置该处深度为 \(0\)，由该处出发更新其他点的深度并使之最小，重复上述操作直至所有叶子结点均被覆盖。
详细细节见代码注释。

代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=1000+114514;

int T, n, s, k;

vector<int> G[MAXN];
int in[MAXN], dist[MAXN], fa[MAXN];
int ans;

struct cmp{
	bool operator()(pii x, pii y){
		return x.first == y.first ? x.second < y.second : x.first < y.first;
	}
};
priority_queue<pii, vector<pii>, cmp> q; //使用堆储存待处理的叶子结点

int rd()
{
	int x = 0, sgn = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	return x * sgn;
}

void init()
{
	memset(in, 0, sizeof(in) );
	memset(dist, 0, sizeof(dist) );
	memset(fa, 0, sizeof(fa) );
	
	for(int i = 0; i < MAXN; ++i) 
		while(!G[i].empty() ) G[i].pop_back();
	
	while(!q.empty()) q.pop();
	
	ans = 0;
}

void get_dis(int s, int fath)
{
	for(int i = 0; i < G[s].size(); ++i)
	{
		int to = G[s][i];
		if(to == fath) continue;
		fa[to] = s;
		dist[to] = dist[s] + 1;
		get_dis(to, s);
	}
}

void update(int s, int fath)
{
	for(int i = 0; i < G[s].size(); ++i)
	{
		int to = G[s][i];
		if(to == fath) continue;
		if(dist[to] > dist[s] + 1) //更新深度，取该点到各个服务器距离的最小值
		{
			dist[to] = dist[s] + 1;
			update(to, s);
		}
	}
}

int main()
{
	T = rd();
	while(T--)
	{
		init();
		n = rd(); s = rd(); k = rd();
		for(int i = 1; i <= n - 1; ++i)
		{
			int x = rd(), y = rd();
			G[x].push_back(y);
			G[y].push_back(x);
			++in[x]; ++in[y];
		}
		get_dis(s, 0);
		for(int i = 1; i <= n; ++i)
			if(in[i] == 1 && dist[i] > k) q.push(make_pair(dist[i], i) ); //若度为1，则该点为叶子结点
		
		while(!q.empty() )
		{
			pii x = q.top(); q.pop();
			int dep = x.first, id = x.second, tmp = k;
			if(dist[id] <= k) continue; //如果更新深度后该点的深度小于等于k，则不需要处理
			while(tmp--) id = fa[id]; //寻找k级祖先
			dist[id] = 0;
			update(id, 0);
			++ans;
		}
		printf("%d\n", ans);
	}
	return 0;
}