把s当作树根，把无根树转化为有根树，然后遍历一个层次图，贪心地取每个叶子结点的第k个父亲节点即可。
1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 4 using namespace std; 5 template<class T> 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<int>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<n;++i) node[i].clear(); 77 for (register int i=1,a,b;i<n;++i) read(a),read(b),addedge(a,b); 78 dfs_dep(s,0); 79 printf("%d ",rush()); 80 } 81 fclose(stdin); 82 fclose(stdout); 83 return 0; 84 }