【SCOI2005】bzoj1086 王室联邦

本文主要是介绍【SCOI2005】bzoj1086 王室联邦，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

从根开始dfs，用一个栈来维护目前还没有分配的点。对于当前处理的点，如果处理完一棵子树之后根的子树中剩下的节点达到 $b$ ，就把这些点弹栈，这个根节点做省会。处理完子树之后把自己加入栈中。因为父亲节点一定比后继节点后入栈，而弹栈的时候会直接清空，也就是把所有后继节点都弹掉，所以不会出现断的情况。这样的话本来剩下的不到 $b$ ，从新子树中剩下的不到 $b$ ，划分出来的省大小都不到 $2b$ 。最后剩下的节点直接扔到最后分出来的省里，大小不超过 $3b$ 。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=2010;
int fir[maxn],ne[maxn],to[maxn],sta[maxn],bel[maxn],cap[maxn],
n,m,tot,top;
void add(int num,int u,int v)
{ne[num]=fir[u];fir[u]=num;to[num]=v;
}
void dfs(int u,int fa,int bot)
{for (int i=fir[u];i;i=ne[i])if (to[i]!=fa){dfs(to[i],u,top);if (top-bot>=m){tot++;while (top>bot) bel[sta[top--]]=tot;cap[tot]=u;}}sta[++top]=u;if (top-bot>=m){tot++;while (top>bot) bel[sta[top--]]=tot;cap[tot]=u;}
}
int main()
{int u,v;scanf("%d%d",&n,&m);for (int i=1;i<n;i++){scanf("%d%d",&u,&v);add(i*2,u,v);add(i*2+1,v,u);}dfs(1,-1,0);while (top) bel[sta[top--]]=tot;printf("%d\n",tot);for (int i=1;i<=n;i++)printf("%d%c",bel[i],i==n?'\n':' ');for (int i=1;i<=tot;i++)printf("%d%c",cap[i],i==tot?'\n':' ');
}