【题目描述】
余人国的国王想重新编制他的国家。
他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成 员来管理。
他的国家有 $n$ 个城市，编号为 $1..n$ 。一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条直接或间接的道路。
为了防止管理太过分散，每个省至少要有 $B$ 个城市，为了能有效的管理，每个省最多只有 $3B$ 个城市。
每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。
但是该省的任意一个城市到达省会所经过的道路上的城市（除了最后一个城市，即该省省会）都必须属于该省。
一个城市可以作为多个省的省会。
聪明的你快帮帮这个国王吧！
【题目链接】
BZOJ 1086 王室联邦 【SCOI 2005】
【解题思路】
这是一道树分块的模板题。
就本题而言，我们将「省」称之为「块」，将「省会」称之为「块根」（这是自己起的名）。
首先要说明的一点是，树分块 并不是 把树分成若干个互不相交的连通块。
同一块中的点不一定是连通的，但在加上「块根」后一定是一个连通块，但「块根」可能不属于这个块，一个点可以作为多个块的「块根」。
这样分块有一个性质：同一块中任意两点间的距离不超过 $S$（块的大小）。
接下来我们说怎么分块。
对树进行 dfs，设过程 $dfs(v)$ 处理 $v$，任务为将 $v$ 的 孩子子树 中所有点分块，并返回 $v$ 的 子树 中未分块的点，但总应保证这些未分块的点与 $v$ 连通，以便父节点处理。
$dfs(v)$ 这样工作：对 $v$ 所有的孩子，递归调用 $dfs$，并接收这个过程中未分块的点，一旦数量超过 $B$，立即将其归成一块，以 $v$ 为块根。
这样显然是合法的，因为这些点都是与孩子连通的，孩子和 $v$ 是连通的，那么加上 块根 $v$ 后一定连通；并且因为孩子返回的点数不会超过 $B$，所以这个块的大小不会超过 $2B$。
最后将剩下的点与 $v$ 一同返回。
返回一些点——这个不好写，但这个过程可以借助一个栈来维护，每次 $dfs$ 时把未分块的点压入栈中，然后返回到上一层时直接从栈中取就可以了。
将刚进入 $dfs$ 时的栈顶称为「临时栈底」，递归对孩子调用 $dfs$，孩子们会把未分块的点放到栈中——这些点总是在「临时栈底」之上的。
所以要分清楚，栈中哪些是和我无关的，哪些点是从孩子返回的。已经分了块的点要从栈中弹出，剩下的放在栈中当做返回即可，记得最后要把 $v$ 本身压栈。
最后一个问题，处理完根节点后可能还会有剩余的点，这些点怎么办呢？这些点的数量一定不超过 $B$，我们之前分的块中点的数量不超过 $2B$，所以我们把它们放到最后一个块中即可，正好满足题目 $[B, 3B]$ 的限制。
【AC代码】
#include <cstdio>
const int MAXN = 1000;
struct Node{
struct Edge *edges;
int blockId;
} nodes[MAXN];
struct Edge{
Node *to;
Edge *next;
Edge(Node *fr, Node *to) : to(to), next(fr->edges) {}
};
inline void link(Node *u, Node *v){
u->edges = new Edge(u, v);
v->edges = new Edge(v, u);
}
int n, B;
Node *S[MAXN];
int top;
int bcnt;
Node *root[MAXN];
void dfs(Node *v, Node *fa = NULL){
int bot = top;
for(Edge *e = v->edges; e; e = e->next) if(e->to != fa){
dfs(e->to, v);
if(top - bot >= B){
while(top > bot) S[--top]->blockId = bcnt;
root[bcnt++] = v;
}
}
S[top++] = v;
}
void solve(){
dfs(nodes);
while(top) S[--top]->blockId = bcnt - 1;
}
int main(){
scanf("%d%d", &n, &B);
for(int i = 0, u, v; i < n - 1; i++){
scanf("%d%d", &u, &v), u--, v--;
link(nodes + u, nodes + v);
}
solve();
printf("%d\n", bcnt);
for(Node *v = nodes; v != nodes + n; v++) printf("%d%c", v->blockId + 1, v != nodes + n - 1 ? ' ' : '\n');
for(int i = 0; i < bcnt; i++) printf("%d%c", int(root[i] - nodes) + 1, i != bcnt - 1 ? ' ' : '\n');
return 0;
}