我以为树分块什么的必有高论，结果居然是个暴力……
方法也很简单，我看下每个节点dfs的时候是否已经大于k个，大于的话我就新开一块。
注意dfs的时候当前节点不能放进子树的块中。
1 #include<bits/stdc++.h> 2 #define N 100010 3 using namespace std; 4 struct Edge{int u,v,next;}G[2*N]; 5 int n,B,top,tot,head[N<<2],cnt,rt[N],block[N],q[N]; 6 inline void addedge(int u,int v){ 7 G[++tot].u=u;G[tot].v=v;G[tot].next=head[u];head[u]=tot; 8 G[++tot].u=v;G[tot].v=u;G[tot].next=head[v];head[v]=tot; 9 } 10 void dfs(int u,int f){ 11 int last=top; 12 for(int i=head[u];i;i=G[i].next){ 13 int v=G[i].v;if(v==f)continue; 14 dfs(v,u); 15 if(top-last>=B){ 16 block[++cnt]=u; 17 for(;top>last;top--)rt[q[top]]=cnt; 18 } 19 } 20 q[++top]=u; 21 } 22 inline int read(){ 23 int f=1,x=0;char ch; 24 do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); 25 do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); 26 return f*x; 27 } 28 int main(){ 29 n=read();B=read(); 30 for(int i=1;i<n;i++){ 31 int x=read(),y=read(); 32 addedge(x,y); 33 } 34 dfs(1,0); 35 while(top)rt[q[top--]]=cnt; 36 printf("%d ",cnt); 37 for(int i=1;i<=n;i++)printf("%d ",rt[i]);puts(""); 38 for(int i=1;i<=cnt;i++)printf("%d ",block[i]);puts(""); 39 return 0; 40 }