简化版题意：

一个国家由\(n\)个城市组成一颗树，要将其划分为\(n\)个省

每个城市大小为\([B,3B]\),每个省有一个省会（不一定要在省内），使得每个省的所有城市到省会的路径上不能经过其他省。

首先我们可以明确，原图中的一颗完整子树一定是满足要求的。

那么我们可以这样思考，维护一个栈，由下至上递归进行合并

若当前子树的城市树已经大于B，那么我们将其合并

这样一次失败的省划分最多余留下的节点为b-1,这样每个块最大大小为2b-1，满足要求

但是，会出现一个问题，有可能当前子树未达到，而加上另一个子树就达到了B，但是按照递归顺序，这两棵子树是不连通的，那应怎么办呢？

我们可以维护一个标记limit，记录递归前栈内元素个数，这样的话就可以有效避免这个问题的发生。

但是，题目为什么要给到3B呢?

这是因为在我们遍历完所有节点后，有可能还剩余一些节点（最多为B个）。这样的话，根据上面的推断，我们可以直接将其并入最后一个块，大小最大为3B-1，符合题目要求。

于是这道题目就愉快的解决辣！

---

贴代码

#include<bits/stdc++.h>

using namespace std;

const int maxn=3e4;

int n,b;

struct cc{

	int to,nex;

}e[maxn];

int head[maxn],cnt,tag[maxn],rt[maxn],tot;

void add(int a,int b)

{

	++cnt;

	e[cnt].to=b;

	e[cnt].nex=head[a];

	head[a]=cnt;

}

stack<int> s;

void dfs(int u,int fa)

{

	int lim=s.size();

	for(int i=head[u];i;i=e[i].nex)

	{

		int v=e[i].to;

		if(v!=fa)

			dfs(v,u);

		if(s.size()-lim>=b)

		{

			rt[++tot]=u;

			while(s.size()>lim){

				tag[s.top()]=tot;

				s.pop();

			}

		}

	}

	s.push(u);

}

int main()

{

	int x,y;

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

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

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

	dfs(1,0);

	if(!tot) rt[++tot]=1;

	while(!s.empty()) tag[s.top()]=tot,s.pop();

	printf("%d\n",tot);

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

		printf("%d ",tag[i]);

	printf("\n");

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

		printf("%d ",rt[i]);

	return 0;

}