[POI 2008] BLO-Blockade

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

封锁一个点后，真正新增损失来自它把图切成的多个连通块；用 Tarjan 求割点时顺手统计每个被切下来的子树大小，就能在线性时间算出每个点造成的访问损失。

OJ: luogu

题目 ID: P3469

难度:提高

标签:图论tarjan割点

创建: 2026-06-20 02:28

更新: 2026-10-23 13:13

前置题目

luogu P3388【模板】割点（割顶）B 明确复用 A 教的「low[v]>=dfn[u] 判割点」这一步来确定删 u 后哪些子树独立成块（B 原文“这正是 Tarjan 割点里 low[v]>=dfn[u] 的含义”），再叠加 A 未教的答案拆两部分（2*(n-1) 直接访问 + 跨连通块访问对计数）。POJ 1144NetworkB 的核心步骤复用 A 教的 Tarjan 割点判定 low[v]>=dfn[u]（A 的 1.cpp 即 if(low[v]>=dfn[u] && u!=root)），回溯时按该判据取出被切下的子树块并计算作废访问贡献 POJ 1523SPFB 明确复用 A 的「low[v]>=dfn[u] 判定割点、每个满足条件的子节点切出一块子网」这一步，回溯时拿 sub_size[v] 累加块间作废访问数，再叠加 2*(n-1) 直接损失与剩余大块贡献

题意

有一张连通无向图，每个点代表一个城镇，每个城镇里正好有一个居民。

原本一共应该发生：

n * (n - 1) 次访问

因为每个人都想访问其他所有人一次。

现在如果封锁某个城镇 u，就会导致：

任何和 u 有关的访问都不可能发生
删掉 u 以后，如果图被分成多个连通块，不同连通块之间的人也无法互相访问

题目要求对每个点 u 输出：

如果封锁 u，最终有多少次访问无法进行

样例图

样例图长这样：

graph G {
  graph [rankdir=LR];
  1 -- 2;
  1 -- 3;
  2 -- 3;
  3 -- 4;
  4 -- 5;
}

从图上就能看出：

点 3 和点 4 是关键位置
封锁 3 时，图会裂成 {1,2} 和 {4,5}
封锁 4 时，图会裂成 {1,2,3} 和 {5}

所以这两个点的答案会比普通点更大。

把所有点都数一遍，可以得到下面这张对照表：

封锁的点	删点后的连通块	割点带来的额外损失	答案
`1`	`{2,3,4,5}` 一整块	0	8
`2`	`{1,3,4,5}` 一整块	0	8
`3`	`{1,2}` 和 `{4,5}`	`2 * 2 * 2 = 8`	16
`4`	`{1,2,3}` 和 `{5}`	`2 * 3 * 1 = 6`	14
`5`	`{1,2,3,4}` 一整块	0	8

表格里“额外损失”一列正是后面要算的东西：只有删点后真的裂成多块时它才不为 0，其余情况答案都等于固定损失 2 * (n - 1) = 8。

思路

先看一个最直接的暴力：

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// brute.cpp：枚举封锁哪个点，直接数删点后的连通块大小。
// 各块之间的访问全部作废，再加上所有“和被封锁点有关”的访问，就是答案。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n, m;
vector<int> g[MAXN];
bool vis[MAXN];

void dfs(int u, int ban, int &cnt) {
    vis[u] = true;
    cnt++;

    for (size_t i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v == ban || vis[v]) {
            continue;
        }
        dfs(v, ban, cnt);
    }
}

long long calc(int ban) {
    for (int i = 1; i <= n; i++) {
        vis[i] = false;
    }

    vector<int> comps;
    for (int i = 1; i <= n; i++) {
        if (i == ban || vis[i]) {
            continue;
        }
        int sz = 0;
        dfs(i, ban, sz);
        comps.push_back(sz);
    }

    long long bad = 2LL * (n - 1);
    for (size_t i = 0; i < comps.size(); i++) {
        for (size_t j = i + 1; j < comps.size(); j++) {
            bad += 2LL * comps[i] * comps[j];
        }
    }
    return bad;
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        g[i].clear();
    }

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) {
        cout << calc(i) << '\n';
    }

    return 0;
}

暴力做法是：

枚举封锁哪个点 u
真的把 u 删掉
重新数删点后的每个连通块大小
统计不同连通块之间一共有多少对访问作废

这个方法容易理解，但每个点都重跑一遍 DFS，复杂度是 $O(n(n+m))$ ，在 $n = 10^5$ 时完全不可行。

（brute.cpp 里 MAXN 只开到 25，它只负责在小图上给后文的对拍当标准答案，不是能提交的版本。）

正式做法的关键是把答案拆成两部分：

所有和 u 直接有关的访问
这部分固定是 2 * (n - 1)
因为别人去 u、以及 u 去别人，这两类访问都作废。
删掉 u 以后，不同连通块之间的访问
这部分只有当 u 是割点时才会额外出现。

注意访问是有方向的：a 去 b 和 b 去 a 是两次不同的访问，所以后面每一对“分属两个块的点”都要乘 2。

所以问题就变成：

删掉点 u 后，会分出哪些连通块？它们大小是多少？

这正是 Tarjan 割点里 low[v] >= dfn[u] 的含义。

如果 u 有一个儿子 v 满足：

low[v] >= dfn[u]

说明删掉 u 以后，v 这棵子树会单独裂成一个连通块，大小就是 sub_size[v]。

于是我们在 DFS 回溯时，把每个这样的“被切下来的块”依次拿出来计数即可。

设这些块的大小依次是：

c1, c2, ..., ck

那么它们和“前面已经切出来的点”之间会新增：

2 * c_i * (前面所有块大小之和)

次作废访问。把同一个块和所有更早的块配对，正好覆盖了块与块之间的全部点对，不会重复也不会漏。

最后还要补上一个“剩余大块”：

它的大小是 n - 1 - (c1 + c2 + ... + ck)

这块和前面所有被切下来的块之间，也会产生同样的双向损失，总共是

2 * S * (n - 1 - S)，其中 S = c1 + c2 + ... + ck

这里容易卡住的一点是：剩下那部分为什么算“一块”？因为删掉 u 之后，u 的祖先方向、以及那些满足 low[v] < dfn[u] 的儿子子树，都还能经过 u 的父亲绕回去，彼此之间仍然连通，所以它们合成一个整体。

顺带说明两个看起来要特判、其实不用特判的边界：

对非根节点 u，如果它不是割点，就没有任何儿子满足 low[v] >= dfn[u]，于是 S = 0，额外损失 2 * 0 * (n - 1) = 0，答案自然退化成 2 * (n - 1)。
对根节点，它的 dfn 最小，每个儿子的子树都满足 low[v] >= dfn[u]，于是 S 恰好就是全部非根点，S = n - 1，剩余大块大小是 n - 1 - S = 0，这部分贡献算成 0。根只有一个儿子时（S = n - 1 且只有一个块），块间配对也是 0，答案回到 2 * (n - 1)，与“删根后图仍连通”一致。所以这里不需要像模板割点那样额外判断 u != root 或子树个数。

把三件事对上号，整道题其实就是：

Tarjan 求割点
同时维护每棵子树大小
在回溯时用这些大小直接算贡献

对应到 main.cpp 里就是：

正文里的量	代码里的变量	含义
固定损失 `2 * (n - 1)`	`answer[u]` 的初值	封锁 `u` 时和 `u` 有关的访问
已经切出来的块大小之和 `S`	`cut_sum[u]`	回溯过程中逐步累加
被切下来的一个块 `c_i`	`sub_size[v]`	`v` 子树的大小
剩余大块 `n - 1 - S`	`n - 1 - cut_sum[u]`	不单独存，直接现算

一行实现细节：因为 $n$ 可以到 $10^5$ ，链状数据会让递归深度爆栈，所以 main.cpp 用显式栈 Frame 手动模拟 DFS，逻辑和递归写法完全一致，st 弹栈的位置就是“回溯”。

代码

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/**
 * 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-06-20 02:28
 * update_at: 2026-10-23 22:33
 */
// P3469 [POI 2008] BLO-Blockade
// 割点 + 子树大小统计，计算封锁每个点后的作废访问数
// 核心：Tarjan 求割点时顺手统计被切下的子树大小，answer[u] = 2*(n-1) + 跨块损失
#include <bits/stdc++.h>
using namespace std;

// 邻接表存图：to 为邻居编号，rev 为反向边在邻接表中的下标（用于跳过父边）
struct Edge {
    int to, rev;
};

const int MAXN = 100005;

int n, m;
vector<Edge> g[MAXN];          // 邻接表

int dfn[MAXN], low[MAXN];      // Tarjan 时间戳 / 能回溯到的最小 dfn
int parent_node[MAXN];         // DFS 树上的父节点
int parent_rev[MAXN];          // 父边反向边在 g[u] 中的下标，用于跳过
int sub_size[MAXN];            // 以 u 为根的子树大小
int child_cnt[MAXN];           // DFS 树上 u 的儿子个数
int dfs_clock;                 // 时间戳计数器

long long cut_sum[MAXN];       // 已被割下的子树块大小之和
long long answer[MAXN];        // 封锁 u 后无法发生的有序访问次数

// 加无向边 (u, v)，rev 互相记录反向边位置
void add_edge(int u, int v) {
    g[u].push_back({v, (int)g[v].size()});
    g[v].push_back({u, (int)g[u].size() - 1});
}

// Tarjan 求割点，同时统计每个点的作废访问数
void tarjan(int u) {
    dfn[u] = low[u] = ++dfs_clock;
    sub_size[u] = 1;
    child_cnt[u] = 0;
    cut_sum[u] = 0;
    answer[u] = 2LL * (n - 1);  // 固定损失：封锁 u 后 u 与外界的 2*(n-1) 次访问全部作废

    for (int i = 0; i < (int)g[u].size(); i++) {
        if (i == parent_rev[u]) continue;  // 跳过回到父节点的反向边
        int v = g[u][i].to;

        if (!dfn[v]) {
            // 树边：递归处理子节点 v
            parent_node[v] = u;
            parent_rev[v] = g[u][i].rev;
            child_cnt[u]++;
            tarjan(v);

            sub_size[u] += sub_size[v];
            low[u] = min(low[u], low[v]);

            // 若 v 子树无法回溯到 u 之前，则删除 u 后 v 子树单独成块
            // 此时 v 子树与 u 的 cut_sum 块之间产生跨块损失
            if (low[v] >= dfn[u]) {
                answer[u] += 2LL * cut_sum[u] * sub_size[v];
                cut_sum[u] += sub_size[v];
            }
        } else if (dfn[v] < dfn[u]) {
            // 后向边：更新 low（只考虑 dfn 比 u 小的，即祖先方向）
            low[u] = min(low[u], dfn[v]);
        }
    }

    // 补上"剩余大块"（u 的祖先方向 + 可回溯子树）与已切下块之间的跨块损失
    answer[u] += 2LL * cut_sum[u] * (n - 1 - cut_sum[u]);
}

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

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
    }

    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            parent_node[i] = 0;
            parent_rev[i] = -1;
            tarjan(i);
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << answer[i] << '\n';
    }

    return 0;
}

复杂度

每个点进出栈一次，每条边在两条链式边里各被处理常数次，所以：

时间复杂度 $O(n+m)$
空间复杂度 $O(n+m)$

总结

这题最重要的转化是：

不要直接去算“还能访问多少次”
而是去算“哪些访问作废了”

一旦改成“作废访问数”，就会自然拆成：

和被封锁点本身有关的固定损失
割点把图切开后，不同块之间的额外损失

于是 Tarjan 的 low[v] >= dfn[u] 不再只是“判割点”，而是直接告诉我们：

有一个大小为 sub_size[v] 的连通块被切下来了

这就是这题的核心。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P3469 [POI 2008] BLO-Blockade

题目描述

There are exactly $n$ towns in Byteotia.

Some towns are connected by bidirectional roads.

There are no crossroads outside towns, though there may be bridges, tunnels and flyovers. Each pair of towns may be connected by at most one direct road. One can get from any town to any other-directly or indirectly.

Each town has exactly one citizen.

For that reason the citizens suffer from loneliness.

It turns out that each citizen would like to pay a visit to every other citizen (in his host’s hometown), and do it exactly once. So exactly $n\cdot (n-1)$ visits should take place.

That’s right, should.

Unfortunately, a general strike of programmers, who demand an emergency purchase of software, is under way.

As an act of protest, the programmers plan to block one town of Byteotia, preventing entering it, leaving it, and even passing through.

As we speak, they are debating which town to choose so that the consequences are most severe.

Task Write a programme that:

reads the Byteotian road system’s description from the standard input, for each town determines, how many visits could take place if this town were not blocked by programmers, writes out the outcome to the standard output.

输入格式

In the first line of the standard input there are two positive integers: $n$ and $m$ ( $1\le n\le 100\ 000$ , $1\le m\le 500\ 000$ ) denoting the number of towns and roads, respectively.

The towns are numbered from 1 to $n$ .

The following $m$ lines contain descriptions of the roads.

Each line contains two integers $a$ and $b$ ( $1\le a<b\le n$ ) and denotes a direct road between towns numbered $a$ and $b$ .

输出格式

Your programme should write out exactly $n$ integers to the standard output, one number per line. The $i^{th}$ line should contain the number of visits that could not take place if the programmers blocked the town no. $i$ .

输入输出样例 #1

输入 #1

text

输出 #1

text

[POI 2008] BLO-Blockade

目录

题意

样例图

思路

代码

复杂度

总结

一图流解析