记录编号	157926	评测结果	AAAAAAAAAA
题目名称	[SCOI 2005]王室联邦	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.199 s
提交时间	2015-04-11 16:41:30	内存使用	3.03 MiB

#include<iostream>
#include<cstdio>
using namespace std;
#define N 100010
int n,m,i,zj1,zj2,zj3;
int sj=1,to[N<<1],ne[N<<1],head[N];
int Root[N],Ret[N],A[N],Num;
inline void addedge(int u,int v)
{
	to[++sj]=v,ne[sj]=head[u],head[u]=sj;
	to[++sj]=u,ne[sj]=head[v],head[v]=sj;
}
void init()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<n;i++)
	scanf("%d%d",&zj1,&zj2),addedge(zj1,zj2);
}
inline void dfs(int x,int y)
{
	int temp=A[0];
	for(int h=head[x];h;h=ne[h])if(to[h]!=y)
	{
		dfs(to[h],x);
		if(A[0]-temp>=m)
		{
			Root[++Num]=x;
			while(A[0]!=temp)
			Ret[A[A[0]--]]=Num;
		}
	}
	A[++A[0]]=x;
}
void work()
{
	while(A[0])Ret[A[A[0]--]]=Num;
	printf("%d\n",Num);
	for(i=1;i<n;i++)printf("%d ",Ret[i]);
	printf("%d\n",Ret[i]);
	for(i=1;i<Num;i++)printf("%d ",Root[i]);
	printf("%d\n",Root[i]);
}
int main()
{
	freopen("bzoj_1086.in","r",stdin);
	freopen("bzoj_1086.out","w",stdout);
	init();
	dfs(1,1);
	work();
	return 0;
}