P2325 [SCOI2005]王室联邦
基础树分块。
这道题卡了我一上午。
(dfs)每一个节点，从叶子节点向上压入栈。设当前节点为(x)，我们记录一下当前栈的大小(tmp)，在遍历(x)的子树，如果遍历完一颗子树后发现当前栈的大小与(tmp)的差值大于等于(b)，那么就把这棵子树的节点划分到同一个省内，并且把省会标位(x)。
对于根节点，栈中会剩余一些节点，我们把这些节点放到最后一个省内，因为剩余的这些节点的数目一定是小于等于(b - 1)的，最后一个省的节点数一定不超过(2b)，所以这么划分是正确的。
#include <bits/stdc++.h>
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 1e3 + 5;
int n, b, t, mod, cnt, now, tot, top, ans1;
int fa[N], vis[N], vst[N], siz[N], col[N], nod[N], sta[N], num[N], out[N], head[N];
struct edge { int nxt, to; } e[N << 1];
void add(int x, int y) {
e[++cnt].nxt = head[x]; head[x] = cnt; e[cnt].to = y; out[x]++;
}
void dfs(int x, int Fa) {
int tmp = top;
for(int i = head[x]; i ; i = e[i].nxt) {
int y = e[i].to; if(y == Fa) continue;
dfs(y, x);
if(top - tmp >= b) {
++now; nod[now] = x;
while(top > tmp) col[sta[top--]] = now;
}
}
sta[++top] = x;
}
int main() {
n = read(); b = read();
for(int i = 1, x, y;i <= n - 1; i++)
x = read(), y = read(), add(x, y), add(y, x);
dfs(1, 0);
while(top) { col[sta[top--]] = now; }
printf("%d
", now);
for(int i = 1;i <= n; i++) printf("%d ", col[i]);
printf("
");
for(int i = 1;i <= now; i++)
if(!nod[i]) printf("1 ");
else printf("%d ", nod[i]);
return 0;
}