删边问题

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

答案拆成与删边无关的基线 T0 加上桥的贡献 s*(C-s):并查集算 T0,迭代式 Tarjan 求桥与 DFS 子树大小,回答每次询问 O(1)。

OJ: roj

题目 ID: 1734

难度:提高+/省选-

标签:图论Tarjan割边并查集cpppython

创建: 2026-10-07 20:30

更新: 2026-10-07 20:30

形式化题目

给一个 nn 个点、mm 条边的无向图,点与边均从 00 开始编号,允许重边与自环。 共 QQ 次询问,第 ii 次给出一个边编号 xx,要求回答:把第 xx 条边删掉之后, 图中有多少无序点对 (u,v)(u, v)(u≠vu \neq v)互不可达。答案对 10001000 取模(题面写的是"保留后三位")。

形式化地,设 GxG_x 是删掉边 xx 后的图,CxC_x 是 GxG_x 上的连通关系,问的是

f(x)=#{{u,v}:u≠v,  (u,v)∉Cx}. f(x) = \#\bigl\{\{u, v\} : u \neq v,\; (u, v) \notin C_x\bigr\}.

注意统计的是全图的不可达点对,删边前就已经不连通的点对也算在内——这一点由样例唯一确定: 样例里点 33 是孤立点,删掉非桥边答案仍是 33 而不是 00。

正解

思路

先处理"删边前"。 不管删哪条边,删之前全图就已经互不可达的点对始终是同一批, 它们的贡献与 xx 无关。把所有连通块的大小记为 s1,s2,…,sks_1, s_2, \dots, s_k(∑si=n\sum s_i = n), 那么块内的点对全部可达、块间的点对全部不可达,于是

T0=(n2)−∑i=1k(si2). T_0 = \binom{n}{2} - \sum_{i=1}^{k} \binom{s_i}{2}.

求每个块的大小用并查集(带大小合并)即可,O((n+m)α)O((n + m)\alpha)。 注意 (n2)\binom{n}{2} 最大约 5×1095 \times 10^9,超过了 int,必须用 64 位整数(long long / Python 任意精度)。 样例里 n=4n = 4,块为 {0,1,2}\{0,1,2\} 与 {3}\{3\},T0=6−3−0=3T_0 = 6 - 3 - 0 = 3。

再看删边带来的变化。 删一条边 xx 只会影响它所在的那个连通块 BB(大小记作 CC)。 把这条边从 BB 中去掉之后:

  • 若 xx 不是桥,BB 仍然连通,块结构一点没变,故 f(x)=T0f(x) = T_0;
  • 若 xx 是桥,BB 被切成两块 B1B_1、B2B_2,大小分别记 ss 与 C−sC - s。 原本 BB 内部两两可达(贡献 00),现在 B1B_1 与 B2B_2 之间的点对全部变成不可达, 而这些点对的数量正是 s⋅(C−s)s \cdot (C - s)。故 f(x)=T0+s(C−s)f(x) = T_0 + s(C - s)。

于是问题变成:对每条边,O(1)O(1) 地回答"它是不是桥",以及"它是桥时切下的那侧有多大"。

判定桥 + 取子树大小。 这是 Tarjan 求桥的标准做法。对图做 DFS,记 dfn[u] 为时间戳、 low[u] 为 uu 的子树里能通过返祖边回到的最小 dfn,则对 DFS 树上的父边 (p,u)(p, u):

边 (p,u) 是桥  ⟺  low[u]>dfn[p]. \text{边 } (p,u) \text{ 是桥} \iff \texttt{low}[u] > \texttt{dfn}[p].

为什么这个判据和"切下来的大小"是同一件事:DFS 树中 uu 的子树恰好就是"删掉父边后 只靠 uu 一侧能找到的点集"。low[u] > dfn[p] 说明这棵子树没有任何一条边能通到 pp 或更上面, 因此它整个被这条边封住,大小就是 sub[u]。所以一次 DFS 同时得到桥的集合与每条桥的 ss, 不需要第二遍遍历。

重边与自环。 这两个是本题最容易写错的地方。

  • 自环永远不是桥(删掉它两个端点仍是同一个点,连通性不变)。Tarjan 里自环表现为 一条 v == u 的边,它的 dfn[v] 已经赋过值,只会用来更新 low[u],不会影响判定。
  • 两条平行边都不是桥:删掉一条后两个端点还能靠另一条连通。判桥时要跳过父边以避免 “儿子顺着树边爬回父亲”;如果按父顶点跳(v == parent[u] 就不看),那么第二条平行边 也会被当成父边忽略掉,于是 low[u] 停留在 dfn[u],low[u] > dfn[p] 成立 → 误判成桥。 正确做法是只跳过父边的编号 pe[u](一条无向边存两条弧 2i,2i+12i, 2i+1, 用 e >> 1 还原边号):这样另一条平行边会被当作返祖边,把 low[u] 拉到 dfn[p],判据不成立。 样例第 0,10,1 两条边就是一对平行边 (0,1)(0,1)、(1,0)(1,0),它们的答案 3,33,3 正好检验这一点。

实现细节:为什么用迭代 DFS。 nn 可达 10510^5 且数据里存在链状图(DFS 深度 10510^5), 递归版 Tarjan 会爆栈。这里用显式栈模拟:栈里存顶点编号,每个点带一个"当前走到哪条出弧"的指针 it[u], it[u] 走完时弹出并回溯——回溯那一瞬间才能拿到子树已经算好的 sub[u] 与 low[u], 正是这一瞬间做"累加子树大小 + 判桥"两件事。所以不能用 BFS 顺序代替,必须保序地模拟 DFS。

顺带一提,删边后"互不可达点对"也可以直接从块的分布算:f(x)=(n2)−∑(si′2)f(x) = \binom{n}{2} - \sum \binom{s'_i}{2}, 其中 s′s' 是删边后的块大小。上式 T0+s(C−s)T_0 + s(C-s) 就是它的化简: 删桥后原来的 (C2)\binom{C}{2} 被换成 (s2)+(C−s2)\binom{s}{2} + \binom{C-s}{2},差值恰为 s(C−s)s(C-s)。

代码

Python 版:

python
#!/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-10-07 20:30
# update_at: 2026-10-07 20:30

import sys

# 类型别名:链式前向星三元组 (head, to, nxt);第 i 条输入边占弧 2i 与 2i+1
# head/nxt 里的 -1 是哨兵,表示"后面没有弧了"
type Star = tuple[list[int], list[int], list[int]]

# 两个等长的 int 列表:(并查集父亲, 每块大小) 或 (桥对应子树根, DFS 子树大小)
type ListPair = tuple[list[int], list[int]]


def build_star(n: int, m: int, ends: list[int]) -> Star:
    """建无向图的链式前向星;第 i 条输入边的两端是 ends[2i]、ends[2i+1]。"""
    head = [-1] * n
    to = [0] * (2 * m)
    nxt = [-1] * (2 * m)
    for i in range(m):
        u, v = ends[2 * i], ends[2 * i + 1]
        e = i << 1
        to[e], nxt[e], head[u] = v, head[u], e
        to[e + 1], nxt[e + 1], head[v] = u, head[v], e + 1
    return head, to, nxt


def find_root(fa: list[int], x: int) -> int:
    """并查集找根(带路径折半);fa 上是父亲,根的父亲是自己。"""
    while fa[x] != x:
        fa[x] = fa[fa[x]]
        x = fa[x]
    return x


def build_dsu(n: int, m: int, ends: list[int]) -> ListPair:
    """并查集 + 每块大小:只有根的 sz 有效,用来 O(1) 取任意点所在连通块大小。"""
    fa = list(range(n))
    sz = [1] * n
    for i in range(m):
        a, b = find_root(fa, ends[2 * i]), find_root(fa, ends[2 * i + 1])
        if a == b:
            continue
        if sz[a] < sz[b]:
            a, b = b, a
        fa[b] = a
        sz[a] += sz[b]
    return fa, sz


def count_unreachable0(n: int, fa: list[int], sz: list[int]) -> int:
    """T0 = C(n,2) - Σ 每块 C(块大小,2):删边前就已经互不可达的无序点对数。"""
    total = n * (n - 1) // 2
    for r in range(n):
        if fa[r] == r:                       # 只在根上统计一次
            total -= sz[r] * (sz[r] - 1) // 2
    return total


def find_bridges(n: int, m: int, star: Star) -> ListPair:
    """迭代式 Tarjan:返回 (bridge_child, sub),对应 C++ 版的同名数组。

    bridge_child[x] = 边 x 是桥时被切下的那侧子树根(否则 -1);sub[v] = DFS 子树点数。
    必须按「父边编号」跳过父边(e >> 1),否则平行重边会被误判成桥;自环不影响连通性。
    """
    head, to, nxt = star
    dfn = [0] * n            # DFS 序,0 表示未访问
    low = [0] * n            # 能回溯到的最小 dfn
    pe = [-1] * n            # DFS 树中的父边编号
    sub = [0] * n            # DFS 树子树点数
    it = head[:]             # 当前出弧指针
    bridge_child = [-1] * m
    timer = 0
    for s in range(n):
        if dfn[s]:
            continue
        timer += 1
        dfn[s] = low[s] = timer
        sub[s] = 1
        stack = [s]
        while stack:
            u = stack[-1]
            e = it[u]
            if e != -1:
                it[u] = nxt[e]
                if (e >> 1) == pe[u]:
                    continue             # 父边的两个方向都不走
                v = to[e]
                if dfn[v] == 0:
                    timer += 1
                    dfn[v] = low[v] = timer
                    sub[v] = 1
                    pe[v] = e >> 1
                    it[v] = head[v]
                    stack.append(v)
                elif dfn[v] < low[u]:
                    low[u] = dfn[v]      # 返祖边(含重边里指向祖先的那一条)
            else:
                stack.pop()              # u 的出弧走完,回溯到父亲 p
                if stack:
                    p = stack[-1]
                    sub[p] += sub[u]
                    if low[u] < low[p]:
                        low[p] = low[u]
                    if low[u] > dfn[p]:                 # 子树回不到 p → 父边是桥
                        bridge_child[pe[u]] = u         # 记下切走的那侧子树根
    return bridge_child, sub


def answer_queries(fa: list[int], sz: list[int], sub: list[int], bridge_child: list[int],
                   unreachable0: int, queries: list[int]) -> list[str]:
    """逐条回答询问:桥的答案 = T0 + s*(C-s),其余边就是 T0;输出只保留后三位。"""
    out: list[str] = []
    for x in queries:
        ans = unreachable0
        cuts = bridge_child[x]
        if cuts >= 0:                              # 是桥:连通块被切成 s 与 C-s 两块
            block = sz[find_root(fa, cuts)]        # 该边所在连通块大小 C
            ans += sub[cuts] * (block - sub[cuts])  # 新增互不可达点对 s*(C-s)
        out.append(str(ans % 1000))                # 题面要求只保留后三位
    return out


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m, Q = next(data), next(data), next(data)

    ends = [next(data) for _ in range(2 * m)]     # 第 i 条边的两端紧挨着
    queries = [next(data) for _ in range(Q)]

    star = build_star(n, m, ends)
    fa, sz = build_dsu(n, m, ends)
    unreachable0 = count_unreachable0(n, fa, sz)
    bridge_child, sub = find_bridges(n, m, star)

    answers = answer_queries(fa, sz, sub, bridge_child, unreachable0, queries)
    sys.stdout.write('\n'.join(answers) + '\n')


if __name__ == "__main__":
    solve()

C++ 版(同一算法,加了自己写的读写缓冲以应对 10610^6 条边的输入量):

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-07 20:30
 * update_at: 2026-10-07 20:30
 */

// 一本通 1734《删边问题》(对应 roj 1734)
//
// 题意:无向图 n 个点 m 条边(点、边从 0 编号,允许重边与自环),Q 次询问,
//       每次给出边编号 x,问删掉这条边之后全图有多少个无序点对 (u, v) 互不可达,
//       答案模 1000 输出。
//
// 关键观察:删一条边只可能把「原本连通的那块」拆开,且只有该边是桥时连通性才变。
//   设该边所在连通块大小为 C,桥把 DFS 树子树部分(大小 s)与其余部分切开,
//   则新增互不可达点对 s * (C - s);删非桥边(重边之一、自环、环上的边)答案不变。
//   于是 ans(x) = T0 + [x 是桥] * s * (C - s),T0 = C(n,2) - Σ C(块大小,2)。
//
// 判定桥用 Tarjan:low[v] > dfn[u] 时树边 (u,v) 是桥。重边必须按「父边编号」跳过,
//   不能按「父顶点」跳过,否则两条平行边会互相看不到、被误判成桥。
//
// 复杂度 O(n + m + Q);n,m,Q 最大 1e5/1e6/8e5,故 DFS 用显式栈迭代实现,防链状图爆栈。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100000 + 10;       // 点编号上界(题面 n <= 1e5)
const int MAXM = 1000000 + 10;      // 边编号上界(题面 m <= 1e6)
const int MAXARC = MAXM * 2 + 10;   // 每条无向边存两条弧

int n, m, Q;

// ---------------- 快速读入 / 输出(1e6 条边 + 8e5 次询问,cin 有超时风险)----------------
namespace FastIO {

const int BUFSIZE = 1 << 16;
char in_buf[BUFSIZE];
ll in_pos = 0, in_len = 0;

// 取一个字符;缓冲区空了就补一次读,文件结束返回 -1
int read_char() {
    if (in_pos == in_len) {
        in_len = fread(in_buf, 1, BUFSIZE, stdin);
        in_pos = 0;
        if (in_len <= 0) return -1;
    }
    return in_buf[in_pos++];
}

// 跳过空白后读一个非负整数
int read_int() {
    int c = read_char();
    while (c != -1 && (c < '0' || c > '9')) c = read_char();
    if (c == -1) return -1;
    int x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = read_char();
    }
    return x;
}

char out_buf[BUFSIZE];
int out_pos = 0;

void flush_out() {
    if (out_pos > 0) {
        fwrite(out_buf, 1, out_pos, stdout);
        out_pos = 0;
    }
}

void write_char(char c) {
    if (out_pos == BUFSIZE) flush_out();
    out_buf[out_pos++] = c;
}

// 答案一定非负且已经模过 1000,逆序放数字再正序输出,末尾补换行
void write_int(ll x) {
    char tmp[8];
    int len = 0;
    if (x == 0) tmp[len++] = '0';
    while (x > 0) {
        tmp[len++] = '0' + x % 10;
        x /= 10;
    }
    while (len > 0) write_char(tmp[--len]);
    write_char('\n');
}

}  // namespace FastIO

// ---------------- 链式前向星:第 i 条输入边对应弧 2i 与 2i+1 ----------------
int head[MAXN];    // head[u] 是 u 的第一条出弧编号,-1 表示无边
int arc_to[MAXARC];  // 弧的终点
int arc_nxt[MAXARC]; // 同一起点的下一条弧
int arc_cnt = 0;

// 加一条无向边 u-v;第 i 条输入边的两条弧编号恰为 2i 与 2i+1
void add_edge(int u, int v) {
    arc_to[arc_cnt] = v;
    arc_nxt[arc_cnt] = head[u];
    head[u] = arc_cnt++;
    arc_to[arc_cnt] = u;
    arc_nxt[arc_cnt] = head[v];
    head[v] = arc_cnt++;
}

// ---------------- 并查集:求连通块大小,算 T0 ----------------
struct DsuNode {
    int fa;  // 父亲,根的父亲是自己
    int sz;  // 只在根上有效:连通块点数
};
DsuNode dsu[MAXN];

int find_root(int x) {
    while (dsu[x].fa != x) {
        dsu[x].fa = dsu[dsu[x].fa].fa;  // 路径折半
        x = dsu[x].fa;
    }
    return x;
}

void merge_node(int a, int b) {
    a = find_root(a);
    b = find_root(b);
    if (a == b) return;
    if (dsu[a].sz < dsu[b].sz) swap(a, b);
    dsu[b].fa = a;
    dsu[a].sz += dsu[b].sz;
}

// ---------------- 每个点在 DFS 树里的信息聚合在一起 ----------------
struct Vertex {
    int dfn;      // DFS 序,0 表示还没访问
    int low;      // 能回溯到的最小 dfn
    int pe;       // DFS 树中的父边编号,-1 表示是根
    int sub;      // DFS 树子树点数
    int it;       // 显式栈 DFS 的当前出弧指针
};
Vertex ver[MAXN];

int bridge_child[MAXM];  // 边编号 -> 它是桥时对应子树根;非桥保持 -1
int dfs_stack[MAXN];     // 显式栈(顶点编号),替代递归

ll unreachable0;  // T0:删边前全图互不可达的无序点对数

void read_input() {
    n = FastIO::read_int();
    m = FastIO::read_int();
    Q = FastIO::read_int();

    for (int i = 0; i < n; i++) {
        head[i] = -1;
        dsu[i].fa = i;
        dsu[i].sz = 1;
        ver[i].dfn = 0;
        ver[i].pe = -1;
    }
    for (int i = 0; i < m; i++) bridge_child[i] = -1;

    for (int i = 0; i < m; i++) {
        int u = FastIO::read_int();
        int v = FastIO::read_int();
        add_edge(u, v);          // 自环/重边原样保留,Tarjan 会正确处理
        merge_node(u, v);
    }
}

// T0 = C(n,2) - Σ 每个连通块 C(块大小,2)
void count_unreachable0() {
    unreachable0 = (ll)n * (n - 1) / 2;
    for (int i = 0; i < n; i++) {
        if (find_root(i) != i) continue;  // 只在根上统计一次
        ll s = dsu[i].sz;
        unreachable0 -= s * (s - 1) / 2;
    }
}

// 迭代式 Tarjan:求桥 + DFS 树子树大小。同一轮 DFS 里完成,二者和桥一一对应。
void find_bridges() {
    int timer = 0;
    for (int s = 0; s < n; s++) {
        if (ver[s].dfn != 0) continue;
        ver[s].dfn = ver[s].low = ++timer;
        ver[s].sub = 1;
        ver[s].it = head[s];
        int top = 0;
        dfs_stack[top++] = s;
        while (top > 0) {
            int u = dfs_stack[top - 1];
            int e = ver[u].it;
            if (e != -1) {
                ver[u].it = arc_nxt[e];
                int id = e >> 1;
                if (id == ver[u].pe) continue;  // 父边跳过:按边编号跳,重边才不会被误判成桥
                int v = arc_to[e];
                if (ver[v].dfn == 0) {
                    ver[v].dfn = ver[v].low = ++timer;
                    ver[v].pe = id;
                    ver[v].sub = 1;
                    ver[v].it = head[v];
                    dfs_stack[top++] = v;
                } else if (ver[v].dfn < ver[u].low) {
                    ver[u].low = ver[v].dfn;  // 返祖边(含重边指向祖先的那条)
                }
            } else {
                top--;  // u 的出弧走完,回溯到父亲 p
                if (top == 0) break;
                int p = dfs_stack[top - 1];
                ver[p].sub += ver[u].sub;
                if (ver[u].low < ver[p].low) ver[p].low = ver[u].low;
                // 子树 u 回不到 p 或更高处 → 父边是桥,子树 u 就是被切下来的一侧
                if (ver[u].low > ver[p].dfn) bridge_child[ver[u].pe] = u;
            }
        }
    }
}

void answer_queries() {
    for (int q = 0; q < Q; q++) {
        int x = FastIO::read_int();
        ll ans = unreachable0;
        int ch = bridge_child[x];
        if (ch >= 0) {
            ll c = dsu[find_root(ch)].sz;  // 该边所在连通块大小
            ll s = ver[ch].sub;            // 被切下来的子树大小
            ans += s * (c - s);
        }
        FastIO::write_int(ans % 1000);
    }
    FastIO::flush_out();
}

int main() {
    read_input();
    count_unreachable0();
    find_bridges();
    answer_queries();
    return 0;
}

复杂度

  • 时间:并查集 O((n+m)α(n))O((n+m)\alpha(n));Tarjan 每条弧恰好被看一次,O(n+m)O(n + m); 每次询问 O(1)O(1) 查表并取模,O(Q)O(Q)。总计 O(n+m+Q)O(n + m + Q)。 题面上限为 n≤105n \le 10^5、m≤106m \le 10^6、Q≤8×105Q \le 8 \times 10^5, C++ 版在 Q=8×105Q = 8 \times 10^5 的两个顶格点上实测 0.06∼0.140.06 \sim 0.14 s(限时 1000 ms)。 Python 版在同样的顶格点上实测 0.550.55 s(点 10)与 1.51.5 s(点 9),后者超过 1000 ms 的限时,有 TLE 风险(算法未降级)。
  • 空间:head、dfn、low、sub 等按点数开,均为 O(n)O(n); 链式前向星的弧数组为 2m2m;bridge_child 按边数开为 O(m)O(m)。合计 O(n+m)O(n + m), 顶格约 2020 MB 量级(限时 256 MB)。
  • 与 Python 解法的关系:main.py 与 main.cpp 是同一算法——链式前向星、 带大小的并查集、迭代式 Tarjan 求桥与子树大小、询问时 s(C−s)s(C-s) 累加。 两版都把桥信息落成一张按边编号索引的表,所以 QQ 次询问都是查表。

总结

  • 把答案拆成"与删边无关的基线 + 单条边的贡献":f(x)=T0+[x 是桥] s(C−s)f(x) = T_0 + [x\text{ 是桥}]\,s(C-s)。 这一拆解把 QQ 次"删边后重新算连通性"降到 O(1)O(1) 查表。
  • 只有桥才改变可达性:删非桥边(环上的边、重边之一、自环)图结构不变,答案就是 T0T_0。
  • 一次 DFS 同时得到桥的集合与切下来的子树大小:sub[u] 天然就是删掉父边后被封住的那一侧, 判据 low[u] > dfn[p] 与"这侧有多大"是同一个条件的两个面。
  • 重边必须按边编号跳过父边,不能按父顶点跳过,否则平行边会被误判成桥;自环始终不是桥。
  • 大图要用迭代 DFS:链状数据下递归深度为 nn,会爆栈;显式栈里保存"当前出弧指针"即可。
  • 计数别用 int:T0T_0 与 s(C−s)s(C-s) 都能到 10910^9 量级,C++ 里必须用 long long。

验证记录

  • 数据来源:本目录数据由素材仓库的 data.py(cyaron 生成器)配合 std.cpp 现场生成, 共 10 个测试点,属于自造数据**,不是官方原数据;题面亦可能是依据公开描述重建的, 因此出题意图(尤其是"统计全图不可达点对、而不是只统计被拆开的两侧"这一读法) 以样例为准,本文档的算法按该读法实现。
  • 样例:题面唯一的样例输入 4 3 3 / 0 1 / 1 0 / 0 2 / 0 1 2, main.cpp 与 main.py 输出均为 3 3 5,与题面输出一致(三组逐行比对全过)。
  • 10 个测试点:main.cpp 与 main.py 逐点跑真实数据并与 .out 比对,全部一致。 其中点 1/2 是最小边界(n=m=Q=1n = m = Q = 1 的自环、n=2n = 2 全森林), 点 8 是 10510^5 点的链(全桥,答案接近 (n2)\binom{n}{2} 量级,用来检验子树大小 ss 的计算), 点 9/10 是 n=105,m=106,Q=8×105n = 10^5, m = 10^6, Q = 8 \times 10^5 同时顶格并专门卡递归爆栈与按父顶点跳边的错解。
  • 随机对拍:另写一份每次询问重建并查集的 O(Q(n+m))O(Q(n+m)) 暴力解作参照,固定种子生成 带重边/自环的小图(n≤9,m≤14n \le 9, m \le 14)跑 250 组、n≤60n \le 60 偏向树结构的图跑 151 组, main.cpp 全部与暴力一致;同一批小图再用 main.py 跑 501 组,也全部一致。
  • 独立复核:素材仓库自带的 std.cpp 与本文档算法等价,但本文档两版解法是重新实现的 (链式前向星数组布局、迭代栈写法、按边编号跳父边三处均独立编写),并非照抄; 两版结论与 std.cpp 在 10 个点上逐点一致。
  • 验收工具:python3 scripts/problem-analysis-tools/accept.py --dry-run 1734 通过 (main.cpp 真实数据 10 个点全 PASS,main.py 10/10)。