传送门 为什么这么做说不太清楚，可以参考PoPoQQQ大佬的博客 PoPoQQQ的题解 注意：DFS过后要把栈里剩余的元素都弹出来并处理，否则样例中1号点的属于的省份为0……
#include<bits/stdc++.h> using namespace std; const int maxn=1002; int n,k; int bel[maxn],root[maxn],cnt=0,st[maxn],top=0; int head[maxn],edge=0; struct EDGE { int v,nxt; }e[maxn<<1]; inline int read() { int x=0;char c=getchar(); while (c<'0'||c>'9') c=getchar(); while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x; } inline void adde(int u,int v) { e[edge].nxt=head[u],e[edge].v=v,head[u]=edge++, e[edge].nxt=head[v],e[edge].v=u,head[v]=edge++; } void dfs(int p,int f) { int now=top; for (int i=head[p];~i;i=e[i].nxt) { int v=e[i].v; if (v==f) continue; dfs(v,p); if (top-now>=k) { root[++cnt]=p; while (top^now) bel[st[top--]]=cnt; } } st[++top]=p; } int main() { // freopen("bzoj 1086.in","r",stdin); memset(head,-1,sizeof(head)); n=read(),k=read(); for (int i=1;i<n;++i) { int u=read(),v=read(); adde(u,v); } dfs(1,0); while (top) bel[st[top--]]=cnt;//ESSENTIAL!!! printf("%d\n",cnt); for (int i=1;i<=n;++i) printf("%d ",bel[i]); puts(""); for (int i=1;i<=cnt;++i) printf("%d ",root[i]); puts(""); return 0; }