图片加载可能有点慢,请跳过题面先看题解,谢谢
一道简单的贪心题,而且根节点已经给你了(\(S\)),这就很好做了。
显然,深度小于等于 \(k\) 的都不用管了(\(S\) 深度为0),那么我们只需要处理深度大于 \(k\) 的叶子节点。
这里有一个显而易见的贪心策略:
每次找一个深度最深的没有被覆盖的叶子节点,然后在它的 \(k\) 级祖先上放置服务器,覆盖服务器的周围 \(k\) 层节点。
反复这个操作直到所有节点都被覆盖。
//made by Hero_of_Someone
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define il inline
#define RG register
using namespace std;
il int gi(){ RG int x=0,q=1; RG char ch=getchar(); while( ( ch<'0' || ch>'9' ) && ch!='-' ) ch=getchar();
if( ch=='-' ) q=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x; }
bool vis[1010];
int T,n,k,s,ans;
int size[1010],fa[1010],que[1010][1010];
int num,head[1010],nxt[2010],to[2010];
il void add(int u,int v){
nxt[++num]=head[u];to[num]=v;head[u]=num;
nxt[++num]=head[v];to[num]=u;head[v]=num;
}
il void dfs(int x,int f,int d){
size[x]=1;fa[x]=f;
for(RG int i=head[x];i;i=nxt[i]){
RG int v=to[i]; if(v==f) continue;
dfs(v,x,d+1); size[x]+=size[v];
}
if(size[x]==1 && d>k) que[d][++que[d][0]]=x;
}
il void init(){
n=gi(),s=gi(),k=gi(),num=0;
memset(que,0,sizeof(que));
memset(vis,0,sizeof(vis));
memset(head,0,sizeof(head));
memset(size,0,sizeof(size));
for(RG int i=1;i<n;i++){
RG int u=gi(),v=gi();
add(u,v);
} dfs(s,0,0);
}
il void Dfs(int x,int f,int d){
vis[x]=1; if(d>=k) return ;
for(RG int i=head[x];i;i=nxt[i]){
RG int v=to[i];
if(v==f) continue;
Dfs(v,x,d+1);
}
}
il void work(){ ans=0;
for(RG int d=n-1;d>k;d--){
for(RG int i=1;i<=que[d][0];i++){
RG int x=que[d][i];
if(vis[x]) continue;
RG int cur=x;
for(RG int j=1;j<=k;j++) cur=fa[cur];
Dfs(cur,0,0);
ans++;
}
}
printf("%d\n",ans);
}
int main(){ T=gi(); while(T--){ init(); work(); } return 0; }