博物馆

GitHub跳转原题关系图 Canvas 关系图返回列表

用点双连通分量树把删点后的最大标记连通块转化为虚树上的路径统计。

OJ: shumeng

题目 ID: CSP202506E

难度:提高+/省选-

标签:点双连通分量虚树LCA

日期: 2026-07-31 16:21

形式化题目

连通无向图，每个节点上可能被标记。施工点 $x$ 被删除后，游客可以住在任意剩余节点，因此最多能参观的博物馆数量等于删除 $x$ 后各连通块中标记数的最大值。对每份攻略（一组标记点），求所有 $x$ 的该最大值之和。

思路

先看暴力做法：枚举每个删除点，对剩余图做连通块搜索：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:58
 */
// brute.cpp：枚举施工点并 BFS 每个连通块，适合小图验证。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int> > graph(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    while (q--) {
        int c;
        cin >> c;
        vector<int> weight(n + 1, 0);
        for (int i = 0; i < c; i++) {
            int x;
            cin >> x;
            weight[x] = 1;
        }
        long long answer = 0;
        for (int removed = 1; removed <= n; removed++) {
            vector<int> visited(n + 1, 0);
            int best = 0;
            for (int start = 1; start <= n; start++) {
                if (start == removed || visited[start]) {
                    continue;
                }
                int current = 0;
                queue<int> que;
                que.push(start);
                visited[start] = 1;
                while (!que.empty()) {
                    int u = que.front();
                    que.pop();
                    current += weight[u];
                    for (int i = 0; i < (int)graph[u].size(); i++) {
                        int v = graph[u][i];
                        if (v != removed && !visited[v]) {
                            visited[v] = 1;
                            que.push(v);
                        }
                    }
                }
                best = max(best, current);
            }
            answer += best;
        }
        cout << answer << '\n';
    }
    return 0;
}

点双树

用 Tarjan 求点双连通分量，建点双树：原图节点和每个点双分量都是树节点，节点属于某个分量就连边。删除原图节点 $x$ 后，点双树删掉 $x$ ，它各相邻分支恰好对应原图中的各个连通块。于是问题变成：在点双树上对每个原图节点 $x$ ，求删去它后各分支标记数的最大值。

虚树压缩

设攻略含 $C$ 个标记点。若不是割点，删除它只影响该点自身的标记，贡献为 $C - [x\text{ 被标记}]$ 。先累加基准 $(n-1)C$ ，再修正那些"能改变答案的割点"——它们只会出现在标记点之间的路径上。

对标记点排序并补上相邻 LCA 后建虚树。对虚树节点 $x$ 记录子树标记数 $sub[x]$ ：

节点 $x$ 的每个虚树子树分支权值为对应孩子的 $sub$ ，父亲方向为 $C - sub[x]$ ；
虚树边中间的普通节点不改变分支构成，整条链上朝向孩子的分支数都相同，可用 DFS 序前缀统计链上的割点个数后批量修正。

代码

cpp

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:58
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000;
const int MAXM = 200000;
const int MAXV = MAXN + MAXM + 5;
const int LOG = 20;

struct Edge {
    int to;
    int id;
};

int n, m, q;
vector<Edge> graph[MAXN + 1];
int edge_u[MAXM + 1];
int edge_v[MAXM + 1];
int discovery[MAXN + 1];
int low[MAXN + 1];
int dfs_clock;
vector<int> edge_stack;

vector<int> block_tree[MAXV];
int total_nodes;
int component_seen[MAXN + 1];
int component_id;
bool is_articulation[MAXV];

int tree_parent[MAXV];
int tree_depth[MAXV];
int tree_tin[MAXV];
int tree_tout[MAXV];
int tree_timer;
int up[LOG][MAXV];
int articulation_prefix[MAXV];

int mark_stamp[MAXV];   // 标记节点最近一次属于哪个查询
int virtual_index[MAXV]; // 虚树节点在原数组中的下标

// 按 DFS 序比较两个节点，用于排序后建虚树
bool tin_less(int x, int y) {
    return tree_tin[x] < tree_tin[y];
}

void add_block() {
    component_id++;
    vector<int> vertices;
    while (true) {
        int edge_id = edge_stack.back();
        edge_stack.pop_back();
        int x = edge_u[edge_id];
        int y = edge_v[edge_id];
        if (component_seen[x] != component_id) {
            component_seen[x] = component_id;
            vertices.push_back(x);
        }
        if (component_seen[y] != component_id) {
            component_seen[y] = component_id;
            vertices.push_back(y);
        }
        if (edge_id == -1) {
            break;
        }
    }
    // The marker -1 is not used; this branch is kept unreachable.
}

void make_block_until(int stop_edge) {
    component_id++;
    vector<int> vertices;
    while (true) {
        int edge_id = edge_stack.back();
        edge_stack.pop_back();
        int x = edge_u[edge_id];
        int y = edge_v[edge_id];
        if (component_seen[x] != component_id) {
            component_seen[x] = component_id;
            vertices.push_back(x);
        }
        if (component_seen[y] != component_id) {
            component_seen[y] = component_id;
            vertices.push_back(y);
        }
        if (edge_id == stop_edge) {
            break;
        }
    }
    total_nodes++;
    int block = total_nodes;
    for (int i = 0; i < (int)vertices.size(); i++) {
        block_tree[block].push_back(vertices[i]);
        block_tree[vertices[i]].push_back(block);
    }
}

void tarjan(int u, int parent_edge) {
    discovery[u] = low[u] = ++dfs_clock;
    for (int i = 0; i < (int)graph[u].size(); i++) {
        int v = graph[u][i].to;
        int edge_id = graph[u][i].id;
        if (edge_id == parent_edge) {
            continue;
        }
        if (discovery[v] == 0) {
            edge_stack.push_back(edge_id);
            tarjan(v, edge_id);
            low[u] = min(low[u], low[v]);
            if (low[v] >= discovery[u]) {
                make_block_until(edge_id);
            }
        } else if (discovery[v] < discovery[u]) {
            edge_stack.push_back(edge_id);
            low[u] = min(low[u], discovery[v]);
        }
    }
}

void build_tree_info() {
    vector<int> iterator_index(total_nodes + 1, 0);
    vector<int> stack_nodes;
    stack_nodes.push_back(1);
    tree_parent[1] = 0;
    tree_depth[1] = 0;
    while (!stack_nodes.empty()) {
        int u = stack_nodes.back();
        if (tree_tin[u] == 0) {
            tree_tin[u] = ++tree_timer;
            articulation_prefix[u] = (u <= n && is_articulation[u]) ? 1 : 0;
            if (tree_parent[u] != 0) {
                articulation_prefix[u] += articulation_prefix[tree_parent[u]];
            }
        }
        if (iterator_index[u] == (int)block_tree[u].size()) {
            tree_tout[u] = tree_timer;
            stack_nodes.pop_back();
            continue;
        }
        int v = block_tree[u][iterator_index[u]++];
        if (v == tree_parent[u]) {
            continue;
        }
        tree_parent[v] = u;
        tree_depth[v] = tree_depth[u] + 1;
        stack_nodes.push_back(v);
    }

    for (int u = 1; u <= total_nodes; u++) {
        up[0][u] = tree_parent[u];
    }
    for (int j = 1; j < LOG; j++) {
        for (int u = 1; u <= total_nodes; u++) {
            up[j][u] = up[j - 1][up[j - 1][u]];
        }
    }
}

bool is_ancestor(int u, int v) {
    return tree_tin[u] <= tree_tin[v] && tree_tout[v] <= tree_tout[u];
}

int lca(int u, int v) {
    if (is_ancestor(u, v)) {
        return u;
    }
    if (is_ancestor(v, u)) {
        return v;
    }
    int x = u;
    for (int j = LOG - 1; j >= 0; j--) {
        if (up[j][x] != 0 && !is_ancestor(up[j][x], v)) {
            x = up[j][x];
        }
    }
    return tree_parent[x];
}

int marked_value(int u, int query_id) {
    return mark_stamp[u] == query_id ? 1 : 0;
}

// 单份攻略：在虚树上统计删去每个割点后各分支标记数的最大值之和
long long solve_query(const vector<int> &marked, int query_id) {
    int count_marked = (int)marked.size();
    vector<int> nodes = marked;
    sort(nodes.begin(), nodes.end(), tin_less);
    int original_size = (int)nodes.size();
    // 补上相邻节点的 LCA，构成虚树节点集合
    for (int i = 1; i < original_size; i++) {
        nodes.push_back(lca(nodes[i - 1], nodes[i]));
    }
    sort(nodes.begin(), nodes.end(), tin_less);
    nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());

    int size = (int)nodes.size();
    for (int i = 0; i < size; i++) {
        virtual_index[nodes[i]] = i;
    }
    vector<int> parent_index(size, -1);
    vector<int> stack_nodes;
    for (int i = 0; i < size; i++) {
        while (!stack_nodes.empty() && !is_ancestor(stack_nodes.back(), nodes[i])) {
            stack_nodes.pop_back();
        }
        if (!stack_nodes.empty()) {
            parent_index[i] = virtual_index[stack_nodes.back()];
        }
        stack_nodes.push_back(nodes[i]);
    }

    vector<int> subtree_count(size, 0);
    for (int i = 0; i < size; i++) {
        subtree_count[i] = marked_value(nodes[i], query_id);
    }
    for (int i = size - 1; i > 0; i--) {
        subtree_count[parent_index[i]] += subtree_count[i];
    }

    vector<int> maximum_child(size, 0);
    for (int i = 1; i < size; i++) {
        int p = parent_index[i];
        maximum_child[p] = max(maximum_child[p], subtree_count[i]);
    }

    // 基准：非割点的贡献恒为 C - w_x（删去它只少一个标记点），累加 n-1 次
    long long answer = 1LL * (n - 1) * count_marked;
    // 修正割点：比较各分支标记数与补集，取最大值
    for (int i = 0; i < size; i++) {
        int u = nodes[i];
        if (u <= n && is_articulation[u]) {
            int best = max(maximum_child[i], count_marked - subtree_count[i]);
            int normal = count_marked - marked_value(u, query_id);
            answer += best - normal;
        }
    }

    // 虚树边中间的普通节点：整条链上分支标记数相同，按割点个数批量统计
    for (int i = 1; i < size; i++) {
        int child = nodes[i];
        int parent = nodes[parent_index[i]];
        int between = articulation_prefix[child] - articulation_prefix[parent]
                      - ((child <= n && is_articulation[child]) ? 1 : 0);
        if (between == 0) {
            continue;
        }
        int branch = subtree_count[i];
        int best = max(branch, count_marked - branch);
        answer += 1LL * between * (best - count_marked);
    }
    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        cin >> edge_u[i] >> edge_v[i];
        graph[edge_u[i]].push_back({edge_v[i], i});
        graph[edge_v[i]].push_back({edge_u[i], i});
    }
    total_nodes = n;
    tarjan(1, 0);
    for (int u = 1; u <= n; u++) {
        is_articulation[u] = block_tree[u].size() > 1;
    }
    build_tree_info();

    for (int query_id = 1; query_id <= q; query_id++) {
        int c;
        cin >> c;
        vector<int> marked(c);
        for (int i = 0; i < c; i++) {
            cin >> marked[i];
            mark_stamp[marked[i]] = query_id;
        }
        cout << solve_query(marked, query_id) << '\n';
    }
    return 0;
}

复杂度

预处理 Tarjan 与 LCA 为 $O(n+m)$ 。设所有攻略的标记点总数为 $S$ ，每份攻略排序建虚树总复杂度 $O(S \log S)$ ，空间复杂度 $O(n+m)$ 。

总结

点双树完整刻画了"删点后连通块的结构"，虚树把"所有标记点之间的路径"压缩出来，使长链上的相同贡献能一次统计，避免了逐个枚举割点。

题目来自第 38 次 CSP 认证 T5，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

西西艾弗岛是历史悠久的旅游胜地，岛上有很多的博物馆。

题目描述

小 C 和小 F 二人正在毕业旅行。他们在深夜抵达了西西艾弗岛。

西西艾弗岛的交通系统由 $n$ 个路口和连接它们的 $m$ 条无向道路组成，每个路口都有一家旅馆可供住宿，小 C 和小 F 今夜可以选择任意一个路口的旅馆入住。

西西艾弗岛上有大量的博物馆，小 C 计划第二天去其中一些博物馆游览。他在网上收集了 $q$ 份不同的一日游攻略，其中第 $i$ 份攻略包含 $c_i$ 个博物馆，分别位于第 $a_{i,1},a_{i,2},\dots,a_{i,c_i}$ 个路口。

正在二人畅想明日美好的游玩体验时，小 F 忽然想起一件事：明天西西艾弗岛的市政施工队会在恰好一个路口处施工，也就是说，明天一整天二人都无法经过该路口。这让今晚住宿地点的选择变得非常重要。具体来说，如果第 $x$ 个路口明天施工，小 C 和小 F 今晚住在第 $u$ 个路口，那么对于一座在第 $v$ 个路口的博物馆，二人能游览它当且仅当存在一条从 $u$ 到 $v$ 的路径不经过 $x$ 。特别地，如果 $x=u$ 或 $x=v$ ，那么这座博物馆是无法被游览的。

小 C 和小 F 都是旅行特种兵，只要选定了一份攻略，他们就会游览这份攻略里所有能游览的博物馆。不过小 F 忘记了明天到底是哪个路口要施工了，他决定把所有可能的情况都推演一遍。对于一份攻略，他规定 $f(x)$ 表示在第 $x$ 个路口明天施工的情况下，两人今晚按照最优策略选择旅馆，明天最多能游览的博物馆数量。

现在小 F 希望对所有 $q$ 份攻略都求出其攻略值 $\sum\limits_{i=1}^nf(i)$ 。由于小 F 计算能力比较差，所以他把地图和攻略都发给了你，希望你帮他算出来。

输入格式

从标准输入读入数据。

输入的第一行包含三个正整数 $n,m,q$ ，分别表示路口的数量，双向道路的数量和攻略的数量。

之后 $m$ 行每行包含两个正整数 $u,v$ ，表示一条路口 $u$ 和路口 $v$ 之间的双向道路。

之后 $q$ 行每行表示一份攻略，第 $i$ 行开头一个正整数 $c_i$ ，随后紧跟 $c_i$ 个两两不同的正整数 $a_{i,1},a_{i,2},\dots,a_{i,c_i}$ ，含义见上。

输出格式

输出到标准输出。

输出 $q$ 行，每行一个正整数，表示每一份攻略对应的攻略值。

input1

output1

样例 1 解释

$f(1)=f(2)=f(3)=f(4)=2$ 。

对于其他的路口都有 $f(i)=3$ 。

子任务

对于所有数据，保证：

$1 \le n,q\le 10^5,m\le 2\times 10^5,\sum\limits_{i=1}^q c_i\le 3\times 10^5$ 。
在一开始所有的路口之间两两可达，两个路口之间至多只有一条道路，且不存在一条道路的起点与终点相同。即所有的路口与道路构成一张简单无向连通图。
每份攻略中博物馆所处的路口两两不同。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务 1（15 分）：保证 $n,q\le 100$ ；
子任务 2（15 分）：保证所有的路口和道路组成一条链；
子任务 3（30 分）：保证 $m=n-1$ ；
子任务 4（40 分）：无特殊限制。

博物馆

目录

形式化题目

思路

点双树

虚树压缩

代码

复杂度

总结