记录编号	150733	评测结果	AAAAAAAAAA
题目名称	[SCOI 2005]王室联邦	最终得分	100
用户昵称	new ioer	是否通过	通过
代码语言	C++	运行时间	0.131 s
提交时间	2015-03-02 16:51:14	内存使用	5.73 MiB

#include<cstdio>
const int maxn=100001,maxm=200000;
bool vis[maxn];
int n,b,top,len,cnt,g[maxn],sta[maxn],siz[maxn],cap[maxn],ans[maxn],to[maxm],next[maxm];
char ch[2000000],*ptr=ch;
void add(int x,int y){
	to[++len]=y,next[len]=g[x],g[x]=len;
}
void in(int &x){
	 x=0;
	 while(*ptr<48) ptr++;
	 while(*ptr>47) x=x*10+*ptr++-48;
}
void dfs(int x){
	sta[top++]=x,vis[x]=1;
	for(int t,i=g[x];i;i=next[i]){
		if(vis[t=to[i]]) continue;
		dfs(t),siz[x]+=siz[t];
		if(siz[x]>=b){
			cap[++cnt]=x;
			register int i=top-1;
			while(sta[i]!=x) ans[sta[i--]]=cnt;
			top=i+1,siz[x]=0;
		}
	}
	++siz[x];
}
int main(){
	freopen("bzoj_1086.in", "r", stdin);
	freopen("bzoj_1086.out", "w", stdout);
	fread(ch,1,2000000,stdin);
	in(n),in(b);
	for(int a,b,i=1;i<n;i++) in(a),in(b),add(a,b),add(b,a);
	dfs(1);
	while(top) ans[sta[--top]]=cnt;
	printf("%d\n",cnt);
	for(int i=1;i<n;i++)  printf("%d ",ans[i]);printf("%d\n",ans[n]);
	for(int i=1;i<cnt;i++)printf("%d ",cap[i]);printf("%d\n",cap[cnt]);
}