「Test」死亡的颂唱者

题意：一棵 $n$ 个节点的树，每条边权值为 $1$，现在每个叶子节点处都有一个人，在 $s$ 节点存在一个基地。现在你可以选择在任意没有基地的节点建造基地，满足 $k$ 秒之内每个人都能到达基地，每个人的移动速度都是 $1$ 个单位每秒，请问建造最少的基地数是多少？

一道暴力贪心题目。

因为 $s$ 点已经存在一个基地，所以我们把 $s$ 点设为根节点进行深搜，统计出每个节点的深度和父亲节点。

因此我们只用考虑深度大于 $k$ 的叶子节点即可(叶子节点用一个 $vector$ 存储，即为入度为 $1$ 的点)。

对于这些节点，我们按深度从大到小枚举，对于每个深度的叶节点，肯定在它上方 $k$ 个位置处建基地最优，因为能覆盖到最多的节点。

因此我们对于每个叶节点向上跳 $k$ 个位置，然后建造基地，暴力将覆盖到的位置打上标记即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<vector>
#define INF 1e9
using namespace std;
const int maxn=1010;
const double Pi=acos(-1.0);
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return;
}
int t,n,s,k,dep[maxn],f[maxn];
int head[maxn],cnt,vis[maxn],indgr[maxn];
struct node
{
	int next;
	int to;
}e[maxn<<1];
vector<int> p[maxn];
void add(int from,int to)
{
	e[++cnt].next=head[from];
	e[cnt].to=to;
	head[from]=cnt;
}
void dfs(int u,int fa)
{
	f[u]=fa;
	dep[u]=dep[fa]+1;
	if(indgr[u]==1&&dep[u]>k)
		p[dep[u]].push_back(u);
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa)
			continue;
		dfs(v,u);
	}
}
void mark(int u,int fa,int depth)
{
	vis[u]=1;
	if(depth>=k)
		return ;
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa)
			continue;
		mark(v,u,depth+1);
	}
}
int solve()
{
	int ans=0;
	for(int d=n-1;d>k;d--)
		for(int i=0;i<(int)p[d].size();i++)
		{
			int u=p[d][i];
			if(vis[u])
				continue;
			int fa=u;
			for(int j=1;j<=k;j++)
				fa=f[fa];
			mark(fa,0,0);
			ans++;
		}
	return ans;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		memset(head,0,sizeof(head));
		memset(indgr,0,sizeof(indgr));
		memset(e,0,sizeof(e));
		memset(vis,0,sizeof(vis));
		memset(f,0,sizeof(f));
		cnt=0;
		for(int i=0;i<=maxn;i++)
			p[i].clear();
		scanf("%d%d%d",&n,&s,&k);
		for(int i=1;i<n;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			indgr[a]++;
			indgr[b]++;
			add(a,b);
			add(b,a);
		}
		dep[0]=-1;
		dfs(s,0);
		printf("%d\n",solve());
	}
	return 0;
}