【BZOJ 1086】[SCOI2005] 王室联邦

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1086

来学习树上莫队的前置技能——树分块
题解让我们来%Po娘：《手把手教你块状树系列》

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000+9;
const int M = N * 2;

int head[N],to[M],nxt[M],stk[M],top;
int num[N],pri[N],n,lim,cnt; 

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void Add_Edge(int u, int v) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

void DFS(int w, int f, int bot) {
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			DFS(to[i],w,top);
			if (top - bot >= lim) {
				pri[++cnt] = w;
				for (int i=top;i>bot;i--) {
					num[stk[i]] = cnt;
				}
				top = bot;
			}
		}
	}
	stk[++top] = w;
}

int main(){
	n = read(); lim = read();
	for (int i=1;i<n;i++) {
		Add_Edge(read(),read());
	}
	
	DFS(1,1,0);
	while (top) {
		num[stk[top--]] = cnt;
	}
	
	printf("%d\n",cnt);
	for (int i=1;i<=n;i++) {
		printf("%d%c",num[i],i==n?'\n':' ');
	}
	for (int i=1;i<=cnt;i++) {
		printf("%d ",pri[i]);
	}
	return 0;
}