【BZOJ1086】【SCOI2005】王室联邦

  DFS，如果点数>=B马上变成一个省，这样保证DFS过程中最大的省城市数是<=2B-1的。

  最后剩下那些没分到省的城市分到最后一个省里，这样城市数是<=3B-2的。

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1010;

int head[maxn],next[maxn<<1],E[maxn<<1],Ecnt;

void Add_Edge(int x,int y) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;}

int cap[maxn],belong[maxn];
int stack[maxn],top;
int n,b,ccnt;

int DFS(int x,int fa)
{
	int sons=0;
	for (int i=head[x];i;i=next[i]) if (E[i]!=fa)
	{
		sons+=DFS(E[i],x);
		if (sons>=b)
		{
			ccnt++;
			cap[ccnt]=x;
			while (sons) belong[stack[top--]]=ccnt,sons--;
		}
	}
	stack[++top]=x;
	return sons+1;
}

int main()
{
	scanf("%d%d",&n,&b);
	for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),Add_Edge(x,y);
	(void)DFS(1,0);
	while (top) belong[stack[top--]]=ccnt;
	printf("%d\n",ccnt);
	for (int i=1;i<=n;i++) printf("%d ",belong[i]);
	printf("\n");
	for (int i=1;i<=ccnt;i++) printf("%d ",cap[i]);
	return 0;
}