[SDOI2018] 战略游戏

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

把删点后 S 是否分裂翻译成圆方树上的路径必经点，再用圆点前缀和与虚树环巡游 O(|S|log n) 回答每次询问

OJ: luogu

题目 ID: P4606

难度:省选/NOI-

标签:圆方树点双连通分量tarjanLCA虚树路径计数

创建: 2026-10-23 13:16

更新: 2026-10-23 14:24

目录

  1. 形式化题目
  2. 暴力解法
    1. 思路
    2. 代码
    3. 复杂度
    4. 瓶颈
  3. 正解
    1. 思路
      1. 代码
      2. 复杂度
    2. 总结

    形式化题目

    给定一张 nn 个点 mm 条边的无向连通图 G=(V,E)G=(V,E)（同一对点之间可能有重边），以及一个点集 S⊆VS\subseteq V，∣S∣⩾2|S|\geqslant 2。

    统计满足下列条件的点 uu 的个数：

    • u∉Su\notin S；
    • 在 GG 中删除 uu 及所有与 uu 关联的边后，存在 a,b∈Sa,b\in S，使 aa 与 bb 不连通。

    共 qq 次询问，每次给出不同的 SS，独立作答。

    暴力解法

    思路

    题面本身就是做法：对每个不在 SS 中的点 uu，真的把它删掉，然后从 SS 中的某个点出发做一次 BFS， 看 SS 里是否还有走不到的点。若有点走不到，说明删 uu 能让 SS 分裂，uu 计入答案。

    这只适合小数据：单次询问要枚举 O(n)O(n) 个 uu，每次 BFS 是 O(n+m)O(n+m)，所以每个询问 O(n(n+m))O(n(n+m))。

    代码

    cpp
    /**
 * 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-23 13:40
 * update_at: 2026-10-23 13:40
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 做法完全照着题面：对每个不在 S 中的点 u，真的把 u 删掉，
// 再从 S 的第一个点做 BFS，看 S 里有没有点走不到。
// 单次询问就要 O(n(n+m))，只有 n 很小时才跑得动，所以只服务对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, m, q;

vector<int> g[MAXN]; // 原图邻接表；重边直接重复存，不影响可达性判断
int in_set[MAXN];    // in_set[x]：x 是否在当前询问的占领集合 S 中
int asked[MAXN];     // 当前询问给出的点集 S，题面保证严格递增
int vis[MAXN];       // vis[x] == cur_tag 表示 x 在本轮 BFS 中已被访问
int cur_tag;         // BFS 轮次标记，避免每轮清空 vis

// 从 start 出发做 BFS，禁止经过 ban 点（ban 已被摧毁）。
void bfs(int start, int ban) {
    queue<int> que;
    cur_tag++;
    vis[start] = cur_tag;
    que.push(start);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (auto v : g[u]) {
            if (v == ban || vis[v] == cur_tag) {
                continue;
            }
            vis[v] = cur_tag;
            que.push(v);
        }
    }
}

void solve_one_case() {
    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);
    }

    cin >> q;
    for (int i = 1; i <= q; i++) {
        int k;
        cin >> k;
        for (int j = 1; j <= n; j++) {
            in_set[j] = 0;
        }
        for (int j = 1; j <= k; j++) {
            cin >> asked[j];
            in_set[asked[j]] = 1;
        }

        int answer = 0;
        for (int u = 1; u <= n; u++) {
            if (in_set[u]) {
                continue; // 只能摧毁没被占领的城市
            }
            bfs(asked[1], u);
            bool broken = false;
            for (int j = 1; j <= k; j++) {
                if (vis[asked[j]] != cur_tag) {
                    broken = true;
                    break;
                }
            }
            if (broken) {
                answer++;
            }
        }
        cout << answer << '\n';
    }
}

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

    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        solve_one_case();
    }
    return 0;
}

    复杂度

    单次询问 O(n(n+m))O(n(n+m))，整组数据 O(q⋅n⋅(n+m))O(q\cdot n\cdot(n+m))；空间 O(n+m)O(n+m)。只适用于 nn 很小的数据，用来理解题意并作为对拍基线。

    瓶颈

    暴力慢的原因是重复劳动：对每个候选 uu 都重新扫一遍全图的边。

    但从答案的定义可以看出，真正可能成为答案的点并不多：

    • 如果删除 uu 后图不连通，说明 uu 是割点；不是割点的点删掉后 GG 依然连通，SS 更不可能分裂。
    • 割点 u∉Su\notin S 是否计入，只取决于 G−{u}G-\{u\} 的各连通块里装了哪些 SS 的点。

    也就是说，问题实际上是「对每个询问，数一数有多少个割点把 SS 切开」。瓶颈从「枚举点 + 判连通」变成了「一个点是否落在 SS 的某两个点之间」 —— 这正是下一步要换掉的东西。

    正解

    思路

    第一步：把「切开 S」变成「被某条路径经过」

    图上的「删一个点」难以批量处理，而树上两点之间的路径是很规整的结构：一个点被若干条路径覆盖，就说明它在这些点对的必经位置上。

    所以关键是把原图换成一棵能表达「必经点」的树，这就是圆方树。

    第二步：建圆方树

    用 Tarjan 求出原图的所有点双连通分量（BCC）：

    • 原图每个点保留为一个圆点，编号 1∼n1\sim n；
    • 每个 BCC 新建一个方点，编号 n+1,…n+1,\dots；
    • 方点与它所在 BCC 内的所有圆点连边。

    因为原图连通，这样构造出的图一定是一棵树，称为圆方树。

    建树时有两个必须注意的实现细节，否则会在特殊数据上出错：

    1. 重边不能被跳掉。判断「是否跳过进入当前点的那条边」只能用边编号（成对存边，e == (in_edge ^ 1)）， 不能用「vv 是父亲」来判断。否则两点之间的两条平行边本应构成一个点双（1 个方点、2 个圆点），会被错并成一条树边。
    2. 递归深度可达 O(n)O(n)。链图上圆方树深度约 2n2n，递归写法实测需要约 16 MiB 栈空间（判题器默认给 64 MiB，安全）。

    下面用题目第二个测试数据说明这棵树的形状。原图有边 1 ⁣− ⁣2,1 ⁣− ⁣3,2 ⁣− ⁣3,1 ⁣− ⁣4,2 ⁣− ⁣5,3 ⁣− ⁣61\!-\!2,1\!-\!3,2\!-\!3,1\!-\!4,2\!-\!5,3\!-\!6， 点双为 {1,2,3}\{1,2,3\}、{1,4}\{1,4\}、{2,5}\{2,5\}、{3,6}\{3,6\}，对应 4 个方点：

    graph G {
  node [fontname="monospace"];
  1 [shape=circle, label="1"];
  2 [shape=circle, label="2"];
  3 [shape=circle, label="3"];
  4 [shape=circle, label="4"];
  5 [shape=circle, label="5"];
  6 [shape=circle, label="6"];
  7 [shape=box, label="B{1,2,3}"];
  8 [shape=box, label="B{1,4}"];
  9 [shape=box, label="B{2,5}"];
  10 [shape=box, label="B{3,6}"];
  7 -- 1; 7 -- 2; 7 -- 3;
  8 -- 1; 8 -- 4;
  9 -- 2; 9 -- 5;
  10 -- 3; 10 -- 6;
}

    圆点用圆形、方点用方框。原图中那对割点和非割点的区别在这里一目了然：割点（1,2,31,2,3）挂在多个方点上， 非割点（4,5,64,5,6）只挂一个方点、成为叶子。

    第三步：路径上的圆点 = 必经点

    在圆方树上有如下对应关系：

    原图中两圆点 x,yx,y 之间的所有简单路径都必须经过的点，恰好是圆方树 x⇝yx\rightsquigarrow y 路径上的圆点。

    为什么？圆方树路径上的每个圆点都是割点（或者端点），删掉它就把 x,yx,y 分到两侧，绕不过去； 而方点代表一个点双，块内任意两点之间总能找到绕开块内其它顶点的走法，所以方点和「块内非路径点」都不是必经点。

    于是原来的条件被改写成一句树上的话：

    uu 能把 SS 中的某两个点分开   ⟺  \iff uu 落在「SS 中某两个点的树路径」上。

    把所有这样的路径并起来，就是包含 SS 的极小连通子树 TT（SS 的虚树 / Steiner 树）。答案就是 TT 中「不该算作 SS 自己」的圆点个数：

    answer=∣T∩圆点∣−∣S∣.\text{answer}=|T\cap\text{圆点}|-|S|.

    减 ∣S∣|S| 的合法性来自一个细节：∣S∣⩾2|S|\geqslant 2，所以 TT 的叶子一定都在 SS 里； 而非割点圆点在圆方树上度数恰为 11，它若出现在 TT 中就只能当叶子，于是必属于 SS。 换句话说，TT 中不属于 SS 的圆点全部是割点，正是要数的那些点。

    第四步：用「圆点前缀 + 环巡游」数子树里的圆点

    给点赋权：圆点权 11，方点权 00。问题变成求极小连通子树的点权和。

    把「点权」下推到「边」上：边 (p,c)(p,c)（cc 为儿子）的权取成 w(c)w(c)。这样路径距离

    dist⁡(u,v)=E(u)+E(v)−2E(lca⁡(u,v))\operatorname{dist}(u,v)=E(u)+E(v)-2E(\operatorname{lca}(u,v))

    就只累加「路径上除最浅点以外」的圆点数，其中

    E(x)=根⇝x 路径上的圆点个数E(x)=\text{根}\rightsquigarrow x \text{ 路径上的圆点个数}

    是可以在圆方树 DFS 时一趟预处理出来的前缀和。

    接着把 SS 按圆方树的 DFS 序（tin）排好，首尾相接环游一圈。经典结论：

    2∑e∈Tw(边)=∑i=1kdist⁡(si,si+1),sk+1=s1.2\sum_{e\in T}w(\text{边})=\sum_{i=1}^{k}\operatorname{dist}(s_i,s_{i+1}),\qquad s_{k+1}=s_1 .

    （TT 中每条边在环游中被跨过恰好两次：进入子树一次、离开一次。）

    而已知 ∑e∈Tw(边)=∣T∩圆点∣−w(rootT)\sum_{e\in T}w(\text{边})=|T\cap\text{圆点}|-w(\text{root}_T)，其中 rootT\text{root}_T 是 TT 中最浅的点。 TT 的最浅点就是 SS 全体点的 LCA，而按 DFS 序排序后，首尾两点的 LCA 恰好等于整个集合的 LCA。于是

    answer=12∑i=1kdist⁡(si,si+1)+w(lca⁡(s1,sk))−∣S∣.\text{answer}=\frac{1}{2}\sum_{i=1}^{k}\operatorname{dist}(s_i,s_{i+1})+w\big(\operatorname{lca}(s_1,s_k)\big)-|S| .

    整条式子只用到了 O(1)O(1) 次 LCA（倍增实现），所以每个询问 O(∣S∣log⁡∣S∣+∣S∣log⁡n)O(|S|\log|S|+|S|\log n)。

    用上面的样例验一遍：S={1,2,6}S=\{1,2,6\}，候选可摧毁点为 u∈{3,4,5}u\in\{3,4,5\}。虚树 TT 含圆点 1,2,6,31,2,6,3 与方点 B{1,2,3},B{3,6}B\{1,2,3\},B\{3,6\}，圆点数 44，减去 ∣S∣=3|S|=3 得 11。 核对：删 33 后点 66 与 1,21,2 断开，计入；删 44 或 55 只孤立自己这个叶子，SS 仍连通，不计入。所以答案为 11。

    代码

    cpp
    /**
 * 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-23 13:36
 * update_at: 2026-10-23 14:12
 */
// 圆方树 + 虚树路径计数。
// 圆方树深度最大约 2n（链图），实测判题器 64MB 栈下递归安全，故 Tarjan 与圆方树遍历直接递归。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 100000 + 5; // 原图圆点数量上限
const int MAXM = 200000 + 5; // 原图边数上限
const int MAXV = 300005;     // 圆方树节点上限：n 个圆点 + 至多 m 个方点
const int MAXLOG = 20;       // 3e5 < 2^19，20 层足够让倍增 LCA 爬到根

int n, m, q;

// 原图：链式前向星。边编号从 0 开始成对分配，e^1 就是它的反向边。
int head[MAXN], to[MAXM * 2], nxt[MAXM * 2], edge_cnt;

// Tarjan 求点双：时间戳、点栈（尚未归属任何点双的点）
int dfn[MAXN], low[MAXN], dfs_clock;
int node_stack[MAXN], stack_top;

int square_cnt;           // 方点个数，方点编号为 n+1 .. n+square_cnt
int total_node;           // 圆方树节点总数 = n + square_cnt
vector<int> tree[MAXV];   // 圆方树邻接表，圆点 1..n，方点 n+1..

// 圆方树上的预处理信息
int tin[MAXV];        // 圆方树的 DFS 序，用来给询问点集排序
int depth[MAXV];      // 圆方树上的深度（边数），供 LCA 使用
int pre_circle[MAXV]; // pre_circle[x]：根到 x 的路径上（含根、含 x）的圆点个数
int up[MAXLOG][MAXV]; // 倍增祖先，up[0][x] 是 x 的父节点，0 表示不存在
int tree_clock;       // 圆方树 DFS 序计数器

// 输入只有非负整数，用 getchar 手写快读，避免多组大数据下 cin 太慢。
int read_int() {
    int c = getchar();
    while (c < '0' || c > '9') {
        c = getchar();
    }
    int x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    return x;
}

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

// 把「点栈顶弹到 u（含），再并上割点 p」的这些点连到一个新建的方点上。
void add_square(int u, int p) {
    square_cnt++;
    int sq = n + square_cnt;
    tree[sq].push_back(p);
    tree[p].push_back(sq);
    while (true) {
        int x = node_stack[stack_top--];
        tree[sq].push_back(x);
        tree[x].push_back(sq);
        if (x == u) {
            break;
        }
    }
}

// Tarjan 求点双并同时建出圆方树。
// 回溯到 u 时若 low[u] >= dfn[p]（p 为 u 的父亲），说明 u 的子树回不到 p 的上面，
// 此时点栈顶弹到 u（含）、再并上 p，就组成一个点双，连到一个新建的方点上。
// 根节点的点双都已在某个儿子的回溯里弹出，返回时把残留在点栈底部的根弹掉即可。
void tarjan(int u, int in_edge) {
    dfn[u] = low[u] = ++dfs_clock;
    node_stack[++stack_top] = u;

    for (int e = head[u]; e != -1; e = nxt[e]) {
        int v = to[e];

        // 只跳过进入 u 的那条边本身，重边必须保留（两条平行边构成一个点双）。
        if (e == (in_edge ^ 1)) {
            continue;
        }

        if (!dfn[v]) {
            tarjan(v, e);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                add_square(v, u);
            }
        }
        // 返祖边只能用祖先的 dfn 更新 low。
        else if (dfn[v] < dfn[u]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

// 圆方树遍历：一趟求出 DFS 序、深度、圆点前缀和、倍增父亲。
void dfs_tree(int u, int p) {
    tin[u] = ++tree_clock;
    up[0][u] = p;
    for (auto v : tree[u]) {
        if (v == p) {
            continue;
        }
        depth[v] = depth[u] + 1;
        // 方点权值为 0，不计入圆点前缀和
        pre_circle[v] = pre_circle[u] + (v <= n ? 1 : 0);
        dfs_tree(v, u);
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) {
        swap(u, v);
    }
    int diff = depth[u] - depth[v];
    for (int j = 0; j < MAXLOG; j++) {
        if ((diff >> j) & 1) {
            u = up[j][u];
        }
    }
    if (u == v) {
        return u;
    }
    for (int j = MAXLOG - 1; j >= 0; j--) {
        if (up[j][u] != up[j][v]) {
            u = up[j][u];
            v = up[j][v];
        }
    }
    return up[0][u];
}

int ask_points[MAXN]; // 当前询问给出的点集，按圆方树 DFS 序排序后用

bool cmp_by_tin(int a, int b) {
    return tin[a] < tin[b];
}

void solve_one_case() {
    n = read_int();
    m = read_int();

    for (int i = 1; i <= n; i++) {
        head[i] = -1;
        dfn[i] = 0;
        low[i] = 0;
    }
    edge_cnt = 0;
    dfs_clock = 0;
    stack_top = 0;

    for (int i = 1; i <= m; i++) {
        int u = read_int();
        int v = read_int();
        add_edge(u, v);
        add_edge(v, u);
    }

    square_cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            stack_top = 0;
            tarjan(i, -1);
            stack_top--; // 根节点残留在点栈底部，弹掉
        }
    }
    total_node = n + square_cnt;

    tree_clock = 0;
    for (int i = 1; i <= total_node; i++) {
        tin[i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        if (!tin[i]) {
            depth[i] = 0;
            pre_circle[i] = 1; // 根一定取圆点，它自己算一个圆点
            dfs_tree(i, 0);
        }
    }

    for (int j = 1; j < MAXLOG; j++) {
        for (int v = 1; v <= total_node; v++) {
            up[j][v] = up[j - 1][up[j - 1][v]];
        }
    }

    q = read_int();
    for (int i = 1; i <= q; i++) {
        int k = read_int();
        for (int j = 0; j < k; j++) {
            ask_points[j] = read_int();
        }
        sort(ask_points, ask_points + k, cmp_by_tin);

        // 环巡游：把 S 按 DFS 序首尾相接，相邻两点距离之和等于
        // 极小连通子树的边权和的两倍。边权定义成「儿子的点权」，
        // 于是边权和 = 子树内圆点数 - 子树根的权值。
        ll sum_dist = 0;
        for (int j = 0; j < k; j++) {
            int u = ask_points[j];
            int v = ask_points[(j + 1) % k];
            int w = lca(u, v);
            sum_dist += pre_circle[u] + pre_circle[v] - 2 * pre_circle[w];
        }

        // S 的虚树根 = DFS 序最小与最大两点的 LCA
        int root_of_tree = lca(ask_points[0], ask_points[k - 1]);
        ll circle_cnt = sum_dist / 2 + (root_of_tree <= n ? 1 : 0);

        // 答案 = 虚树上的圆点数 - |S|（S 自身的点不可能是被摧毁的城市）
        printf("%lld\n", circle_cnt - k);
    }

    // 多组数据之间清空圆方树，避免与下一组混淆
    for (int i = 1; i <= total_node; i++) {
        tree[i].clear();
    }
}

int main() {
    int T = read_int();
    for (int tc = 1; tc <= T; tc++) {
        solve_one_case();
    }
    return 0;
}

    复杂度

    • 建圆方树：O(n+m)O(n+m)；
    • 圆方树 DFS（tin、depth、圆点前缀、倍增父亲）：O(n+m)O(n+m)；
    • 倍增 LCA 表：O((n+m)log⁡(n+m))O((n+m)\log(n+m))；
    • 每个询问：O(∣S∣log⁡∣S∣+∣S∣log⁡n)O(|S|\log|S|+|S|\log n)。

    整组数据 O((n+m)log⁡(n+m)+∑∣S∣log⁡n)O\big((n+m)\log(n+m)+\sum|S|\log n\big)，空间 O((n+m)log⁡(n+m))O((n+m)\log(n+m))。

    总结

    本题的核心是换模型：原问题是「删点后 SS 是否分裂」，逐点判定只能做到 O(n(n+m))O(n(n+m))； 一旦把「删点」换成「必经点」，再把必经点换成「圆方树上的路径覆盖」，问题就变成了一道树上路径并的计数题， 用「圆点权 11 / 方点权 00」+ LCA 前缀和 + 按 DFS 序环巡游，每次询问 O(∣S∣log⁡n)O(|S|\log n) 即可。

    三个容易踩坑的实现点：

    1. 重边必须靠边编号而不是父节点判断，否则点双会被算错；
    2. 圆方树深度可达 2n2n，递归 DFS 的栈需求要先按最深链实测（本题判题器 64 MiB 栈下安全）；
    3. 答案是「圆点个数 −∣S∣-|S|」，别忘减 ∣S∣|S|，也别把 SS 自己的点算进去。