题目描述
“余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成员来管理。
他的国家有n个城市，编号为1..n。一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条直接或间接的道路。为了防止管理太过分散，每个省至少要有B个城市，为了能有效的管理，每个省最多只有3B个城市。
每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。但是该省的任意一个城市到达省会所经过的道路上的城市（除了最后一个城市，即该省省会）都必须属于该省。
一个城市可以作为多个省的省会。
聪明的你快帮帮这个国王吧！
输入输出格式
输入格式：
第一行包含两个数N，B（1<=N<=1000, 1 <= B <= N）。接下来N－1行，每行描述一条边，包含两个数，即这条边连接的两个城市的编号。
输出格式：
如果无法满足国王的要求，输出0。否则第一行输出数K，表示你给出的划分方案中省的个数，编号为1..K。第二行输出N个数，第I个数表示编号为I的城市属于的省的编号，第三行输出K个数，表示这K个省的省会的城市编号，如果有多种方案，你可以输出任意一种。
输入输出样例
输入样例#1：
8 2
1 2
2 3
1 8
8 7
8 6
4 6
6 5
输出样例#1：
3
2 1 1 3 3 3 3 2
2 1 8
题目大意：将树分成若干块，每块大小为[B,3*B]。
题解：一开始xjb做，二分分的块的大小，然后dfs分块，10分...
这样做发现个问题，块不连通怎么办？就是说一个块，它的一半在一个节点左子树底部，
另一半在右子树上面...然后看的题解..发现是个树上分块..还专门叫做..王室联邦分块。
挖坑现学...
对于以x为根的子树，如果它的大小（不包含x，这与块的连通性有关）>=B，就把它分成一个块，
如果不满足，就把它们划分到等待区，累计在根节点，等待与它的兄弟子树合并成一块。如果合并
上兄弟子树大小还<B，那么就一直累计想上传，向上传还有多少在等待区的节点。那么就是说，
如果以x为根不包含x的子树大小>=B，直接合并成一块，否则累计到根节点，准备和它的兄弟子树
合并，不能合并一直向上累计，代码中这是用栈实现的。如果累计到根，那么就把这些在等待区
的节点和距离根最近的块合并。不用担心合并后节点数>3*B,因为在等待区的节点的个数一定是<B,
距离根最近的块的大小是>=B,绝不会>=2*B,因为一旦>=B,立即合并为一块。所以等待区的点和
距离根最近块合并相当于B+2*B,最大就是3B，不会超过。合并时递归到最底层，从树的最下面
开始合并，这样避免了之前开始说的不连通的问题，之前说的不包含x是因为，如果以x为根的子树为
1,2,3。如果1,2，x合并，3被x所在的块堵住，不能与其他的块合并。具体实现时，每递归到一个x，
记录此时的栈顶作为相对栈底，然后再搜它的某一个子节点，如果搜完子节点后的栈顶-相对栈底>=B,
将栈中栈顶到相对栈底的所有元素合并为一块，并出栈。搜完这个点的所有子树，将这个点压入栈中。
最后会在栈中有剩余元素，弹出合并。
代码：
#include<cstdio> #define maxn 10005 using namespace std; int n,b,x,y,cnt,top,sumedge; int head[maxn],sta[maxn],belong[maxn],root[maxn]; struct Edge{ int x,y,nxt; Edge(int x=0,int y=0,int nxt=0): x(x),y(y),nxt(nxt){} }edge[maxn<<1]; void add(int x,int y){ edge[++sumedge]=Edge(x,y,head[x]); head[x]=sumedge; } void dfs(int x,int fa){ int bottom=top; for(int i=head[x];i;i=edge[i].nxt){ int v=edge[i].y; if(v==fa)continue; dfs(v,x); if(top-bottom>=b){ root[++cnt]=x; for(;top!=bottom;top--) belong[sta[top]]=cnt; } } sta[++top]=x; }
int main(){ scanf("%d%d",&n,&b); for(int i=1;i<n;i++){ int x,y; scanf("%d%d",&x,&y); add(x,y);add(y,x); } dfs(1,0); for(;top;top--)belong[sta[top]]=cnt; printf("%d ",cnt); for(int i=1;i<=n;i++)printf("%d ",belong[i]);putchar(' '); for(int i=1;i<=cnt;i++)printf("%d ",root[i]);putchar(' '); return 0; }