Description：

给一棵树，要求把他分成很多块，每个块有一个特殊点，特殊点可以不在块内，但是从这个块中的每个点到特殊点的路径必须都在这个块中，要求块大小在 $B\sim 3B$ ，输出方案。

$1\leqslant n\leqslant 1000$

Solution：

使用 $dfs$ ，在进入某棵子树的时候把所有点压进一个栈里，注意要记录一下当前栈顶防止弹掉子树之外的点，每次回溯到这个点的时候检查一下如果栈内元素个数大于等于 $B$ 就拿出来分一块，这样我们如何每个块内元素不会超过 $2B-2$ ，最后还剩不超过 $B-1$ 个随便给谁就行了。

注意因为要尽可能地把高的点留给上面因此最后把根加进栈。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,B;

#define MAXN 1010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int stack[MAXN],top = 0;

int ins[MAXN],tot = 0,cap[MAXN];

void dfs(int k,int fa)

{

	int bot = top;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa)continue;

		dfs(e[i].to,k);

		if(top - bot >= B)

		{

			++tot;cap[tot] = k;

			while(top > bot)

			{

				int t = stack[top--];

				ins[t] = tot;

			}

		}

	}

	stack[++top] = k;

	return;

}

int main()

{

	scanf("%d%d",&n,&B);

	int x,y;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&x,&y);

		add(x,y);

	}

	dfs(1,0);

	for(int i = 1;i <= top;++i)ins[stack[i]] = tot;

	cout << tot << endl;

	for(int i = 1;i <= n;++i)printf("%d ",ins[i]);cout << endl;

	for(int i = 1;i <= tot;++i)printf("%d ",cap[i]);cout << endl;

	return 0;

}