[SCOI2005]王室联邦

Problem

“余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成员来管理。他的国家有 (n) 个城市，编号为 (1dots n)。一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条直接或间接的道路。

为了防止管理太过分散，每个省至少要有 (B) 个城市，为了能有效的管理，每个省最多只有 (3 imes B) 个城市。

每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。但是该省的任意一个城市到达省会所经过的道路上的城市（除了最后一个城市，即该省省会）都必须属于该省。

一个城市可以作为多个省的省会。

数据范围 (nleq 3000)。

Sol + Code

每次 DFS 一棵子树，记录没有被标号的节点。如果某一个时刻节点数 (geq B)，此时标号，并选择根作为省会，这样子标号必然满足标号节点 (<2 imes B)。有可能遍历完子树后剩下 (<B) 的节点没有被标号，此时把根放进来，这些点依赖根的祖先来解决了。如果这个根是整个树的根，由于按照之前的策略，把这些点并入最后一次划分的组里，显然这样仍然满足条件，节点数 (<3 imes B)。复杂度 (mathcal O(n))。

#include <bits/stdc++.h>
const int N = 1005;
int n, B, id[N], core[N], tot = 0;
struct Edge { int v, nxt; } e[N * 2];
int G[N], edges = 0;
void adde(int u, int v) {
	e[edges++] = (Edge){v, G[u]}; G[u] = edges - 1;
}
int st[N], top = 0;
void dfs(int u, int f) {
	int tmp = top;
	for (int i = G[u]; ~i; i = e[i].nxt) {
		int v = e[i].v;
		if (v == f) continue;
		dfs(v, u);
		if (top - tmp >= B) {
			core[++tot] = u;
			while (top > tmp) id[st[--top]] = tot;
		}
	}
	st[top++] = u;
}
int main() {
	scanf("%d%d", &n, &B);
	memset(G, -1, sizeof G);
	for (int i = 1; i < n; i++) {
		int u, v; scanf("%d%d", &u, &v);
		adde(u, v), adde(v, u);
	}
	dfs(1, 0);
	while (top) id[st[--top]] = tot;
	printf("%d
", tot);
	for (int i = 1; i <= n; i++) printf("%d ", id[i]);
	puts("");
	for (int i = 1; i <= tot; i++) printf("%d ", core[i]); 
	return 0;
}