记录编号	147349	评测结果	AAAAAAAAAA
题目名称	[SCOI 2005]王室联邦	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.271 s
提交时间	2015-01-30 13:34:01	内存使用	3.07 MiB

/*====================Asm.Def========================*/
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <memory.h>
#include <vector>
#include <list>
//#include <iostream>
//#include <map>
using namespace std;
template <typename T>inline void getd(T &x){
	char ch = getchar();bool neg = 0;
	while(!isdigit(ch) && ch != '-')ch = getchar();
	if(ch == '-')ch = getchar(), neg = 1;
	x = ch - '0';
	while(isdigit(ch = getchar()))x = x * 10 + ch - '0';
	if(neg)x = -x;
}
/*======================================================*/
typedef long long LL;
const int maxn = 100002;

vector<int> adj[maxn];
int N, B, Bcnt = 0, ans[maxn], size[maxn], cap[maxn], St[maxn], S_it = 0;
bool vis[maxn];

inline void init(){
	getd(N), getd(B);
	if(N < B){
		printf("0\n");
		exit(0);
	}
	int a, b, i;
	for(i = 1;i < N;++i){
		getd(a), getd(b);
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
}

void dfs(int cur){
	St[S_it++] = cur;
	vis[cur] = true;
	for(vector<int>::iterator it = adj[cur].begin();it != adj[cur].end();++it){
		if(vis[*it])continue;
		dfs(*it);
		size[cur] += size[*it];
		if(size[cur] >= B){
			cap[++Bcnt] = cur;
			register int i = S_it - 1;
			while(St[i] != cur)ans[St[i--]] = Bcnt;
			S_it = i + 1;
			size[cur] = 0;
		}
	}
	++size[cur];
}

int main(){
	//#undef DEBUG
	#if defined DEBUG
	freopen("test", "r", stdin);
	freopen("output.txt", "w", stdout);
	#else
	freopen("bzoj_1086.in", "r", stdin);
	freopen("bzoj_1086.out", "w", stdout);
	#endif
	init();
	
	int i;
	dfs(1);
	while(S_it)ans[St[--S_it]] = Bcnt;
	
	printf("%d\n", Bcnt);
	for(i = 1;i < N;++i)printf("%d ", ans[i]);printf("%d\n", ans[N]);
	for(i = 1;i < Bcnt;++i)printf("%d ", cap[i]);printf("%d\n", cap[Bcnt]);
	
	#if defined DEBUG
	printf("\n%.2lfs\n", (double)clock()/CLOCKS_PER_SEC);
	#endif
	return 0;
}