记录编号	148849	评测结果	AAAAAAAAAA
题目名称	[SCOI 2005]王室联邦	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.316 s
提交时间	2015-02-15 21:45:36	内存使用	8.33 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define Maxn 300010
using namespace std;
int n,B,belong[Maxn],root[Maxn],cnt=0,siz[Maxn],dfsn[Maxn],tot=0;
vector<int> G[Maxn];
void dfs(int x,int tp){
    dfsn[++tot]=x;
    for(int i=0;i<G[x].size();i++){
        if(G[x][i]==tp) continue;
        dfs(G[x][i],x);
        siz[x]+=siz[G[x][i]];
        if(siz[x]>=B){
            root[++cnt]=x;
            for(tot;tot&&dfsn[tot]!=x;tot--) belong[dfsn[tot]]=cnt;
            siz[x]=0;
        }
    }
    siz[x]++;
}
int main(){
	freopen("bzoj_1086.in","r",stdin);
	freopen("bzoj_1086.out","w",stdout);
    scanf("%d%d",&n,&B);
    for(int i=1,x,y;i<n;i++){
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    if(n<B) puts("0");
    else{
        dfs(1,1);
        while(tot) belong[dfsn[tot]]=cnt,tot--;
        printf("%d\n",cnt);
        for(int i=1;i<=n;i++) printf("%d ",belong[i]); printf("\n");
        for(int i=1;i<=cnt;i++) printf("%d ",root[i]); printf("\n");
    }
    return 0;
}