「一本通 3.6 练习 5」Blockade

形式化题目

给定无向连通图 $G=(V,E)$ ， $|V|=n$ 、 $|E|=m$ ，无重边、无自环。对每个顶点 $i$ ，删去 $i$ 及所有与它关联的边，统计此时互不连通的有序点对 $(u,v)$ （ $u \ne v$ ，即以 $u$ 为起点或以 $v$ 为起点的两条都算一次）的个数并输出。

题面样例 $n=5$ 、删去点 $1$ 后剩余 $4$ 个点依然连通，答案却是 $8=2\times 4$ ，这确认了点对按有序计数：删去 $i$ 后 $i$ 自己成了孤立点，仅" $i$ 与其余每个点失联"这一项就有 $2(n-1)$ 。

正解

思路

第一步：把问题化简成"块的大小"

删去 $i$ 后，剩下的 $n-1$ 个点被切成若干连通块 $B_1,\dots,B_k$ ，大小记作 $s_1,\dots,s_k$ ，于是 $\sum_j s_j = n-1$ 。

失联的有序点对只有两类：

$i$ 与其它点。 $i$ 已经没有任何边，与 $n-1$ 个点全部失联，贡献固定为 $2(n-1)$ 。
其它点之间。两个点失联，当且仅当它们落在不同的块里。对每个块对 $(B_a,B_b)$ 都有 $2s_as_b$ 个有序点对，合计 $2\sum_{a<b}s_as_b$ 。

第二项用多项式恒等式展开，把“两两配对”变成“平方和”：

2\sum_{a<b}s_as_b=\Big(\sum_j s_j\Big)^2-\sum_j s_j^2=(n-1)^2-\sum_j s_j^2 .

记 $\operatorname{sq}(i)=\sum_j s_j^2$ ，答案就是

\operatorname{ans}(i)=(n-1)^2-\operatorname{sq}(i)+2(n-1).

这一步的关键认识是：答案只取决于删点后各连通块的大小分布，与图的具体连边方式无关。所以问题从"枚举 $n$ 次删点"变成了"一次求出所有 $\operatorname{sq}(i)$ "。

第二步：块的形态由 DFS 树刻画

任取一棵 DFS 树（不指定根，从任意点开始即可）。对树边 $u\to c$ ，令

\operatorname{low}[c]=\min\Big(\operatorname{dfn}[c],\ \min_{(x,y)\ \text{为回边},\ x\in T_c}\operatorname{dfn}[y],\ \min_{c'\ \text{为}\ c\ \text{的儿子}}\operatorname{low}[c']\Big).

即 $T_c$ 里所有点能通过回边"往上跳"到达的最小 $\operatorname{dfn}$ 。若 low[c] >= dfn[u]，说明 $T_c$ 中没有任何点能绕开 $u$ 到达 $u$ 的祖先方向——这正是 Tarjan 的割点判据。于是删去 $u$ 后：

每个满足 low[c] >= dfn[u] 的儿子 $c$ ，其子树 $T_c$ 整体独立成一块，大小是 $\text{size}[c]$ ；
剩下的所有点（ $u$ 的祖先及不在这些子树中的点）合成最后一块。

把满足条件的儿子子树大小之和记作 $\text{cut}[u]$ ，最后一块的大小就是 $n-1-\text{cut}[u]$ ，因此

\operatorname{sq}(u)=\sum_{c:\ \operatorname{low}[c]\ \ge\ \operatorname{dfn}[u]}\text{size}[c]^2+\big(n-1-\text{cut}[u]\big)^2 .

注意非割点不需要特判：此时求和为空、 $\text{cut}[u]=0$ ， $\operatorname{sq}(u)=(n-1)^2$ ，答案退化成 $2(n-1)$ ，与第一步的结论一致。

第三步：为什么块恰好是这些子树

$T_c$ 内部连通： $T_c$ 内的点靠树边相连，树边不会离开 $T_c$ 。
$T_c$ 与外部无边：若存在边 $(x,y)$ ， $x\in T_c$ 而 $y\notin T_c$ 且 $y\ne u$ ，则 $y$ 必是 $u$ 的祖先（DFS 树的性质），这条回边会把 low[x] 压到 $\operatorname{dfn}[y]<\operatorname{dfn}[u]$ ，与 low[c] >= dfn[u] 矛盾。

所以 $T_c$ 在删去 $u$ 之后自成一个连通块，并且不同 $T_c$ 之间也没有边相连。这两条性质合起来保证上面的块划分既不重不漏。

根的情况不需要额外判断。设 $u$ 是它所在 DFS 树的根，则 $\operatorname{dfn}[u]=1$ 最小，low[c] >= dfn[u] 对每个儿子都自动成立：

若 $u$ 不是割点，它只有一个儿子，cut[u] = n-1，外部块大小为 $0$ ，得 $\operatorname{sq}(u)=(n-1)^2$ ；
若 $u$ 是割点，它有至少两个儿子，每个儿子都切出一块，外部块大小同样为 $0$ 。

两种情形下 $n-1-\operatorname{cut}[u]$ 要么等于真实的外部块大小，要么恰好为 $0$ ，而 $0^2$ 不影响求和，所以公式对根同样成立。

第四步：一次 DFS 同时算出所有块

size[c] 需要对整张图只做一次 DFS。技巧在于按 $\operatorname{dfn}$ 从大到小遍历所有点——这恰好是 DFS 的出栈顺序，此时儿子必定比父亲先处理完，于是 size[parent] += size[child] 一遍就能算出全部子树大小，不需要显式回溯栈，也不需要第二次 DFS。

由于 $n\le 10^5$ 、 $m\le 5\times10^5$ ，DFS 深度可能达到 $10^5$ ，递归写法会爆栈（Python 调 setrecursionlimit 也救不了 C 栈），因此实现用显式栈迭代：栈中元素是 (u, i)，表示"点 $u$ 正在看它的第 $i$ 条邻边"；i 前进代替递归下降，i 越界时出栈代替递归返回。

有一处细节容易写错：low 必须在出栈时回传给父亲，而不是入栈时。因为只有到出栈时， $T_u$ 才全部处理完，low[u] 才是终值。另外，用回边松弛时取的是 dfn[v] 而不是 low[v]。

样例推演

对题面样例（三角形 $1\text{-}2\text{-}3$ 接链 $3\text{-}4\text{-}5$ ）逐点列出块的大小，可以看到公式如何产生输出：

删掉的点 $u$	各连通块（点集）	块大小 $s$	$\sum s^2$	$2\sum_{a<b}s_as_b$	答案
1	{2,3,4,5}	4	16	0	8
2	{1,3,4,5}	4	16	0	8
3	{1,2} / {4,5}	2, 2	8	8	16
4	{1,2,3} / {5}	3, 1	10	6	14
5	{1,2,3,4}	4	16	0	8

表格逐列给出：删点后剩余点被切成的块、每块大小、平方和、跨块有序点对数（ $=(n-1)^2-\sum s^2$ ），以及加上 $2(n-1)=8$ 之后的最终答案。

重点观察第 3、4 行。点 $3$ 被删时图断成两块各 $2$ 个点，跨块的 $2\times2\times2=8$ 个点对失联；而点 $1$ 、 $2$ 、 $5$ 不是割点， $\sum s^2=(n-1)^2$ ，跨块项为 $0$ ，答案只剩 $8$ 。这正是"非割点无需特判"的具体体现。

对应到 Tarjan：删点 $3$ 时，儿子 $4$ 的子树 $\{4,5\}$ 满足 low[4] >= dfn[3]，切出 $\text{cut}[3]=2$ ；最后一块大小 $5-1-2=2$ 。删点 $4$ 时儿子 $5$ 切出 $\text{cut}[4]=1$ ，最后一块大小 $3$ 。

代码

Python 版：

python

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#!/usr/bin/env python3
# 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-09-30 16:20
# update_at: 2026-09-30 16:29

import sys

NONE = 0  # 点编号从 1 开始，0 既是"没有父点"也天然是合法的列表越界哨兵


def tarjan(adj: list[list[int]], n: int) -> tuple[list[int], list[int], list[int]]:
    """迭代 Tarjan，返回长度 n+1 的 dfn / low / parent（下标 0 空着不用）。"""
    dfn, low, parent = [0] * (n + 1), [0] * (n + 1), [0] * (n + 1)
    timer = 0
    for root in range(1, n + 1):
        if dfn[root]:                                    # 图可能不连通，逐块起搜
            continue
        timer += 1
        dfn[root] = low[root] = timer
        stack = [(root, 0)]                              # (点, 下一个待看的邻边下标)
        while stack:
            u, i = stack[-1]
            if i < len(adj[u]):
                stack[-1] = (u, i + 1)
                v = adj[u][i]
                if dfn[v] == 0:
                    timer += 1
                    dfn[v] = low[v] = timer
                    parent[v] = u
                    stack.append((v, 0))
                elif v != parent[u]:                     # 回边；父边不参与 low 的松弛
                    low[u] = min(low[u], dfn[v])
            else:
                stack.pop()
                p = parent[u]
                if p != NONE:
                    low[p] = min(low[p], low[u])         # 出栈时把子点的 low 回传
    return dfn, low, parent


def block_squares(dfn: list[int], low: list[int], parent: list[int], n: int) -> list[int]:
    """sq[u] = 删掉 u 后各连通块大小的平方和（不含 u 自己那一份）。

    按 dfn 从大到小遍历，等价于 DFS 出栈顺序：儿子一定比父亲先被处理，
    所以子树大小能直接往父亲身上累加，不需要额外的回溯栈。
    """
    sq = [0] * (n + 1)
    size = [1] * (n + 1)
    cut = [0] * (n + 1)                                  # 已被 u 切出的子树大小之和
    for u in sorted(range(1, n + 1), key=dfn.__getitem__, reverse=True):
        p = parent[u]
        if p == NONE:
            continue
        if low[u] >= dfn[p]:                             # 子树 u 被 p 整块切出去
            sq[p] += size[u] ** 2
            cut[p] += size[u]
        size[p] += size[u]
    for u in range(1, n + 1):
        sq[u] += (n - 1 - cut[u]) ** 2                   # 祖先方向剩下的点合成最后一块
    return sq


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    adj: list[list[int]] = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = next(data), next(data)
        adj[u].append(v)
        adj[v].append(u)
    dfn, low, parent = tarjan(adj, n)
    sq = block_squares(dfn, low, parent, n)
    # 跨块点对 = (n-1)^2 - sq[u]（有序）；再加上 u 与其余 n-1 个点各自失联。
    print('\n'.join(str((n - 1) ** 2 - sq[u] + 2 * (n - 1)) for u in range(1, n + 1)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-10-05 06:19
 * update_at: 2026-10-05 06:19
 */

// roj 1526 Blockade：删点后失联有序点对统计。
// 答案只由删点后各连通块大小的平方和决定，用一次迭代 Tarjan 求出每个割点切出的子树即可。

#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 100005; // n <= 10^5
const int MAXM = 500005; // m <= 5 * 10^5

// 链式前向星，点编号与边编号都从 1 开始，0 表示空
int head[MAXN];      // head[u]：以 u 为起点的第一条边编号
int to[2 * MAXM];    // to[e]：第 e 条边的另一端点
int nxt[2 * MAXM];   // nxt[e]：第 e 条边的下一条边编号
int edge_cnt = 0;

ll dfn[MAXN];        // dfn[u]：DFS 序
ll low[MAXN];        // low[u]：子树 T_u 内通过回边能到达的最小 dfn
ll parent[MAXN];     // parent[u]：DFS 树上的父亲，根为 0
ll sub_size[MAXN];   // sub_size[u]：T_u 的子树大小
ll cut[MAXN];        // cut[u]：被 u 切出去的子树大小之和（low[c] >= dfn[u] 的儿子 c）
ll sq[MAXN];         // sq[u]：删去 u 后各连通块大小的平方和
ll order[MAXN];      // order[t]：dfn 为 t 的点，便于按 dfn 逆序处理
ll dfn_cnt = 0;      // 已分配的 dfn 个数

// 迭代 DFS 的手写栈：stk_u 存点，stk_e 存该点下一条待看的边编号
int stk_u[MAXN];
int stk_e[MAXN];
int top = 0;

void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 迭代 Tarjan：一次 DFS 求出 dfn / low / parent，不用递归，深链不会爆栈。
void tarjan(ll n) {
    ll timer = 0;
    for (int root = 1; root <= n; root++) {
        if (dfn[root] != 0) {
            continue; // 图不连通时逐块起搜
        }
        timer++;
        dfn[root] = timer;
        low[root] = timer;
        order[timer] = root;
        parent[root] = 0;

        top = 0;
        top++;
        stk_u[top] = root;
        stk_e[top] = head[root];

        while (top > 0) {
            int u = stk_u[top];
            int e = stk_e[top];
            if (e != 0) {
                stk_e[top] = nxt[e]; // 这条边看完了，指针后移
                int v = to[e];
                if (dfn[v] == 0) {
                    timer++;
                    dfn[v] = timer;
                    low[v] = timer;
                    order[timer] = v;
                    parent[v] = u;
                    top++;
                    stk_u[top] = v;
                    stk_e[top] = head[v];
                } else if (v != parent[u]) {
                    // 回边：用 dfn[v] 而不是 low[v] 松弛
                    if (dfn[v] < low[u]) {
                        low[u] = dfn[v];
                    }
                }
            } else {
                top--; // u 的邻边看完，u 出栈
                int p = parent[u];
                if (p != 0 && low[u] < low[p]) {
                    low[p] = low[u]; // 出栈时才把子点的 low 回传给父亲
                }
            }
        }
    }
    dfn_cnt = timer;
}

// 按 dfn 从大到小（即 DFS 出栈顺序）累加子树大小，同时算出每个点的 sq。
// 儿子一定比父亲先处理，所以子树大小直接往父亲身上加，不需要额外的回溯。
void calc_blocks(ll n) {
    for (int u = 1; u <= n; u++) {
        sub_size[u] = 1;
        cut[u] = 0;
        sq[u] = 0;
    }
    for (ll t = dfn_cnt; t >= 1; t--) {
        int u = order[t];
        int p = parent[u];

        // 不是被切出的子树，剩下的点（祖先方向）合成最后一块
        ll rest = n - 1 - cut[u];
        sq[u] += rest * rest;

        if (p != 0) {
            if (low[u] >= dfn[p]) {
                // 子树 u 被 p 整块切出去
                sq[p] += sub_size[u] * sub_size[u];
                cut[p] += sub_size[u];
            }
            sub_size[p] += sub_size[u];
        }
    }
}

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

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

    tarjan(n);
    calc_blocks(n);

    // 跨块有序点对 = (n-1)^2 - sq[u]，再加上 u 与其余 n-1 个点各自失联
    for (int u = 1; u <= n; u++) {
        ll ans = (n - 1) * (n - 1) - sq[u] + 2 * (n - 1);
        cout << ans << "\n";
    }

    return 0;
}

代码分三层：tarjan 只负责填 dfn/low/parent；block_squares 按 $\operatorname{dfn}$ 逆序一次遍历算出每个点的 $\operatorname{sq}$ ；solve 只做读入、调用和输出。

复杂度

时间：迭代 Tarjan 中每条边只被看两次， $O(n+m)$ ；按 $\operatorname{dfn}$ 排序 $O(n\log n)$ ；其余 $O(n)$ 。总体 $O(n\log n+m)$ ，主导项与 Tarjan 正解同阶。
空间：邻接表 $O(n+m)$ ，dfn/low/parent/size/sq/cut 各 $O(n)$ 。

总结

本题的推导可以压成一句话：删点后的失联点对数只由各连通块大小的平方和决定，而每个割点切出的块正是它 DFS 树上满足 low[c] >= dfn[u] 的那些子树。

因此解题分两步：先用朴素计数推导出 $\operatorname{ans}(i)=(n-1)^2-\operatorname{sq}(i)+2(n-1)$ ，把问题归约为求 $\operatorname{sq}(i)$ ；再用一次迭代 Tarjan 求出所有子树大小，并按 $\operatorname{dfn}$ 逆序累加，同时得到 $\text{cut}[u]$ ，最后补上大小 $n-1-\text{cut}[u]$ 的外部块。

需要特别注意的边界：非割点不需要特判（公式自然退化到 $2(n-1)$ ）；深链数据必须用显式栈而不是递归。

图示解析

这张图串起本题从建模到得到答案的主线：

text

1
2
3
4
5
6
7
8删掉点 i 后统计失联有序点对
`- 失联只发生在"不同连通块"之间
   |- i 与其它 n-1 个点：固定贡献 2(n-1)
   `- 其它点之间：(n-1)^2 - sum(s_j^2)
      `- 于是只要求 sq[i] = 各块大小平方和
         `- Tarjan：low[c] >= dfn[i] 的儿子子树整体成块
            |- 块大小 = size[c]
            `- 剩下的祖先方向合成一块 = n-1-cut[i]

先看第一层分支： $i$ 自己造成的那 $2(n-1)$ 与块的大小分布无关，所以整道题的难点被压缩成"求每个点的各块大小平方和"。再顺着第二层的分支往下：块不是靠枚举删点得到的，而是靠 DFS 树上 low[c] >= dfn[i] 这个判据一次性认出所有子树块，剩下的一整块用 $n-1-\text{cut}[i]$ 补齐。这样每个点都能在同一棵 DFS 树上算出 $\operatorname{sq}(i)$ ，不需要对每个 $i$ 重新搜一遍图。