树上分块
对于每个子树维护siz
大于B就把这个子树和当前的省作为一块丢掉（这一块一定小于2*B,否则一定会在这个子树的内部再分块）
最后剩下的点在下面找一个子树丢进去就行了,必定满足条件
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N=2005;
int n,B,en,h[N],St[N],belong[N],St_size,siz[N],home[N],hcnt;
struct Edge{
int b,next;
}e[N];
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
void DFS(int u,int fa){
St[++St_size]=u;
for(int i=h[u];i;i=e[i].next){
int v=e[i].b;
if(v==fa)continue;
DFS(v,u);
if(siz[u]+siz[v]>=B){
siz[u]=0;
home[++hcnt]=u;
while(St[St_size]!=u)belong[St[St_size--]]=hcnt;
}
else siz[u]+=siz[v];
}
siz[u]++;
}
void Paint(int u,int fa,int col){
if(!belong[u])belong[u]=col;
else col=belong[u];
for(int i=h[u];i;i=e[i].next){
int v=e[i].b;
if(v!=fa)Paint(v,u,col);
}
}
int main(){
freopen("1086.in","r",stdin);
freopen("1086.out","w",stdout);
scanf("%d %d",&n,&B);
if(n<B){puts("0");return 0;}
for(int i=1;i<n;i++){
int u,v;
scanf("%d %d",&u,&v);
AddEdge(u,v);
AddEdge(v,u);
}
DFS(1,0);
if(!hcnt)home[++hcnt]=1;
Paint(1,0,hcnt);
printf("%d\n",hcnt);
for(int i=1;i<=n;i++)printf("%d ",belong[i]);
putchar('\n');
for(int i=1;i<=hcnt;i++)printf("%d ",home[i]);
putchar('\n');
return 0;
}
评论 (0)
