[SCOI 2005] 王室联邦

题目大意

一个 nn 个节点的树,将点划分为若干块,每块的大小最少为 bb,最大为 3b3b。同时,为每一块选一个节点,使得块中所有节点到这个特殊节点的路径上的点(特殊节点本身除外)均在这一块内。给定树,输出任意一种划分方案(可能无解)。

1n1,000, 1bn1 \leqslant n \leqslant 1,000, \ 1 \leqslant b \leqslant n

题目链接

【SCOI 2005】王室联邦 - Luogu 2325

题解

当且仅当 b>nb > n 时无解。有解时,对树进行 dfs,每当某一点的一些子树大小超过了 bb,就分成一块,并令该点为新分的块的特殊节点。dfs 后,可能会剩一些节点没有块,再 dfs 一遍划给旁边的块就行了。

代码

一开始交的代码没有特判无解,居然就 AC 了。。。

那堆 DBG 是因为一开始把 stack 写成了 queue。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <cstdio>
#include <stack>
// #define DBG
const int MAXN = 1005;
struct Edge;
struct Node {
Edge *firstEdge;
int belong, size, id;
} N[MAXN];
struct Edge {
Node *u, *v;
Edge *next;
Edge(Node *u, Node *v) : u(u), v(v), next(u->firstEdge) {}
};
int cap[MAXN], proCnt;
void addEdge(int u, int v) {
#ifdef DBG
printf("edge: %d <--> %d\n", u, v);
#endif
N[u].firstEdge = new Edge(&N[u], &N[v]);
N[v].firstEdge = new Edge(&N[v], &N[u]);
}
int b;
void dfs(Node *u, Node *fa = NULL) {
#ifdef DBG
printf("dfs(%d), fa = %d\n", u->id, fa ? fa->id : 0);
#endif
static std::stack<Node *> s;
s.push(u);
for (Edge *e = u->firstEdge; e; e = e->next) {
#ifdef DBG
printf("dfs-edge: %d --> %d\n", u->id, e->v->id);
#endif
if (e->v == fa) continue;
dfs(e->v, u);
#ifdef DBG
printf("dfs(%d)size = %d\n", u->id, u->size);
#endif
if (u->size + e->v->size >= b) {
u->size = 0;
cap[++proCnt] = u->id;
while (s.top() != u) s.top()->belong = proCnt, s.pop();
} else u->size += e->v->size;
}
u->size++;
#ifdef DBG
printf("dfs-end(%d)\n", u->id);
#endif
}
void paint(Node *u, Node *fa = NULL, int p = proCnt) {
if (u->belong) p = u->belong;
else u->belong = p;
for (Edge *e = u->firstEdge; e; e = e->next) {
if (e->v != fa) paint(e->v, u, p);
}
}
int main() {
int n;
scanf("%d %d", &n, &b);
if (b > n) {
puts("0");
return 0;
}
for (int i = 1; i <= n; i++) N[i].id = i;
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
addEdge(u, v);
}
dfs(&N[1]);
if (!proCnt) cap[++proCnt] = 1;
paint(&N[1]);
printf("%d\n", proCnt);
for (int i = 1; i <= n; i++) printf("%d%c", N[i].belong, i == n ? '\n' : ' ');
for (int i = 1; i <= proCnt; i++) printf("%d%c", cap[i], i == proCnt ? '\n' : ' ');
return 0;
}