把s当作树根，把无根树转化为有根树，然后遍历一个层次图，贪心地取每个叶子结点的第k个父亲节点即可。
1 #include2 #include 3 #include 4 using namespace std; 5 template inline void read(T &_a){ 6 bool f=0;int _ch=getchar();_a=0; 7 while(_ch<'0' || _ch>'9'){ if(_ch=='-')f=1;_ch=getchar();} 8 while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();} 9 if(f)_a=-_a;10 }11 12 const int maxn=1001;13 struct edge{ int to,next;}w[maxn<<1];14 int T,n,s,k,egcnt,head[maxn],nowu,nowcnt,dep[maxn],fa[maxn],deg[maxn];15 bool vis[maxn];16 vector node[maxn];17 18 inline void addedge(int from,int to)19 {20 w[++egcnt].to=to;21 w[egcnt].next=head[from];22 head[from]=egcnt;23 w[++egcnt].to=from;24 w[egcnt].next=head[to];25 head[to]=egcnt;26 ++deg[from];27 ++deg[to];28 }29 30 void dfs_dep(int u,int fr)31 {32 dep[u]=dep[fr]+1;33 fa[u]=fr;34 if(deg[u]==1) node[dep[u]].push_back(u);35 for (register int i=head[u];i;i=w[i].next)36 if(dep[w[i].to]==-1) dfs_dep(w[i].to,u);37 }38 39 void dfs(int u,int fr,int cnt)40 {41 vis[u]=true;42 if(cnt==k) return ;43 for (register int i=head[u];i;i=w[i].next)44 if(w[i].to!=fr) dfs(w[i].to,u,cnt+1);45 }46 47 inline int rush()48 {49 int res=0;50 for (register int i=n-1;i>k;--i)51 {52 for (register int v=node[i].size()-1;v>=0;--v)53 if(!vis[node[i][v]])54 {55 ++res;56 int u=node[i][v];57 for (register int j=1;j<=k;++j) u=fa[u];58 dfs(u,0,0);59 }60 }61 return res;62 }63 64 int main()65 {66 freopen("singer.in","r",stdin);67 freopen("singer.out","w",stdout);68 for (read(T);T;--T)69 {70 memset(head,0,sizeof(head));71 memset(vis,0,sizeof(vis));72 memset(deg,0,sizeof(deg));73 memset(dep,-1,sizeof(dep));74 egcnt=0;75 read(n); read(s); read(k);76 for (register int i=0;i