[文章目录]
Description
“余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成员来管理。他的国家有n个城市，编号为1..n。一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条直接或间接的道路。为了防止管理太过分散，每个省至少要有B个城市，为了能有效的管理，每个省最多只有3B个城市。每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。但是该省的任意一个城市到达省会所经过的道路上的城市（除了最后一个城市，即该省省会）都必须属于该省。一个城市可以作为多个省的省会。聪明的你快帮帮这个国王吧！
感觉类似构造。
可以将一个节点的儿子为根的子树变为一个省，省会为该节点，尽管他们并不联通。
那么，可以尝试构造一种方法使得每个节点在dfs回溯的时候仅有小于b个节点没有处理。
将每个儿子的子树没有处理的节点放入一个栈中，一旦个数超过b，将其变为一个省。最后回溯的时候一定仅有小于b个节点没有处理。又因为每个儿子剩下的节点个数小于b，所以每个省的节点个数小于2b，最后把根节点连着的没有处理的节点全扔到最后一个省中，仍然合法。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,b,k,ans[1100],sh[1100];
int head[1100],to[2100],nxt[2100],cnt;
void add(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
int z[1100],top;
void dfs(int x,int pre)
{
int tmp=top;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=pre)
{
dfs(to[i],x);
if(top-tmp>=b)
{
k++;
sh[k]=x;
while(top!=tmp) ans[z[top--]]=k;
}
}
z[++top]=x;
if(top-tmp>=b)
{
k++;
sh[k]=x;
while(top!=tmp) ans[z[top--]]=k;
}
}
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); add(y,x);
}
dfs(1,0);
while(top) ans[z[top--]]=k;
printf("%d\n",k);
for(int i=1;i<=n;++i)
printf("%d%c",ans[i],i==n?'\n':' ');
for(int i=1;i<=k;++i)
printf("%d%c",sh[i],i==k?'\n':' ');
return 0;
}