[SCOI 2005] 王室联邦

发表于2017-04-02更新于2020-08-06

题目大意

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

1⩽n⩽1,000, 1⩽b⩽n1 \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;
}