一张图只有一棵最小生成树要算时，Kruskal 已经足够。如果每条边都要问一次“必须保留我，最小费用是多少”，重新跑二十万次 Kruskal 就不够了。

609E 把这些问题压到同一棵树上：加进指定边，形成唯一环，再删掉环上原树路径中的最大边。 每次强制保留一条边是独立问题，不是把所有指定边一起保留。先读并查集与改路、电网规划与最小生成树，再接上倍增与 LCA。

官方题目与约束

题目为 Codeforces 609E Minimum spanning tree for each edge。这里用原创例子解释方法，不复述完整题面；难度与标签来自官方题库 API，核对日期为 2026-10-13。

项目 官方约定
难度、标签 2100；data structures、dfs and similar、dsu、graphs、trees
图 连通无向带权图；没有自环或重边
顶点 n 1 ≤ n ≤ 200000
边 m n−1 ≤ m ≤ 200000
边权 1 到 1000000000
每条边的答案 包含这条边的生成树中，最小的总边权
输出顺序 按输入边编号，每条边一行
限制 2 秒、256 MB

n=1 时合法输入只能有 m=0，程序不输出任何答案；不要为了“至少有一条边”而读不存在的数据。

朴素方法的不足

对一条指定边 e，先把它加入并查集，再按权重扫描其余边，确实能求包含 e 的最优生成树。但逐边重复扫描要花 O(m²) 量级的工作，还没有算重复排序。

问题不在一次 Kruskal 太慢，而在每次询问都丢掉了图的结构。我们先固定任意一棵 MST，记作 T，总权重为 W。树上任意两点只有一条简单路径，新增一条边后也只有一个环。这是可复用的结构。

从唯一环得到候选答案

指定边 e=(u,v,w) 不在 T 中时，加进 e 会形成一个环：e 加上 T 中从 u 到 v 的路径。必须保留 e，因此删边只能从原树路径中选。要让总权重最小，就删除路径上最重的一条边，设其权重为 M。

候选答案是 W+w−M。原树边也满足这个公式：它的两个端点之间的树路径只有它自己，M=w，答案就是 W。

原树总权重W = 10

边权 2、3、5。

必须保留的新边w = 6

连接顶点 1 与 4。

原路径最大边M = 5

最优费用：10 + 6 − 5 = 11。

四个顶点的树路径边权为2、3、5，加入权重6的指定边后删除权重5的原树边
原创手算示意，不是官方样例。橙色边必须保留，虚线标出被替换的原树边。查看原图

同一张四顶点图再加入两条边，逐条询问如下。T 取 1—2、2—3、3—4；每一行都重新考虑一棵生成树，不累积前一行的替换。

指定边 w T 中的端点路径边权 M 最小总费用
1—2 2 2 2 10
2—3 3 3 3 10
3—4 5 5 5 10
1—3 4 2、3 3 11
1—4 6 2、3、5 5 11
2—4 5 3、5 5 10

环替换为什么就是最优解

构造一棵费用为 W+w−M 的树，只能证明这个费用可以达到，还需要排除更便宜的方案。

对非树边 e，考虑任意一棵包含 e 的生成树 S。删除 e 后，S 分成两块 A、B，u 与 v 分别在两块中。T 中 u 到 v 的路径一定跨过这个割，取其中一条跨割边 f。它的权重不超过这条路径的最大值 M。

把 f 加回 S−e，得到一棵生成树，因此费用不能小于 MST 的 W：

weight(S)−w+w(f) ≥ W。

移项后，weight(S) ≥ W+w−w(f) ≥ W+w−M。上节的环替换又恰好达到这个下界，所以候选答案就是最优值。若 e 本来就在 T 中，T 已经是包含它的最优树，答案 W；公式也给出 W。

证明方向 用了什么事实 得到什么
构造上界 树加一条非树边产生唯一环 可以达到 W+w−M
证明下界 任意强制树删 e 得割；T 的端点路径跨割 所有方案至少 W+w−M
原树边 T 本身满足强制要求 答案 W

等权替换不等于所有 MST 都需要它

例子中 2—4 的权重等于路径最大值 5，因此答案仍为 10。这说明它出现在至少一棵 MST 中，不说明它在我们选定的 T 中，更不说明它在所有 MST 中。

Kruskal 遇到相同权重，可以选出不同的 T；答案仍相同，因为上面的证明适用于任意一棵 MST。也不要把这题叫作“严格次小生成树”：答案可以等于 W，且原树边的答案本来就是 W。要进一步区分“所有 MST 都必选”，可接上 160D 的等权分组与桥判定。

  1. 固定原 MST 与总费用

    只做一次 Kruskal，不累积前一次询问的替换。

  2. 查询原树路径最大边

    保留指定边，删除唯一环中允许删除的最大原树边。

  3. 输出费用而不是必选性

    等于 W 只证明至少一棵 MST 可选，不证明每棵都必须选。

自检：答案等于 W，是否说明这条边在所有最小生成树中？

不是。它只说明存在一棵包含这条边的 MST。例子里的 3—4 与 2—4 可以交换；选中的一棵 MST 并不能代表所有最优方案。

用倍增查询路径最大边

以顶点 1 为根，定义 up[k][v] 为 v 向上走 2^k 步到达的祖先，mx[k][v] 为这段上行路径的最大边权。这里储存的是边权，不是顶点编号，也不是整个子树最大值。

状态 定义或转移
up[0][v] v 的父亲
mx[0][v] v 到父亲的边权；根记 0
up[k][v] up[k−1][up[k−1][v]]
mx[k][v] max(mx[k−1][v], mx[k−1][up[k−1][v]])

查询先把较深的端点提到同一深度，沿途累积最大值。若此时端点相同，就结束；否则从大到小尝试同时跳跃，只跳到不同的祖先，最后把两条连接 LCA 的边也计入。

mx 初始值使用 0，是因为官方边权为正。扩展到允许负权的题时，需要重新设计空路径的单位元，例如负无穷，不能原封不动照搬。

完整 C++17 实现

Kruskal 用边的数组下标保留输入顺序；生成树遍历使用显式栈，避免二十万顶点长链触发递归栈溢出。并查集也采用迭代路径压缩。所有费用、路径最大边和答案都使用 long long。

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
#include <algorithm>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
using namespace std;

using ll = long long;
struct Edge { int u, v; ll w; };
struct DSU {
    vector<int> p, size;
    explicit DSU(int n) : p(n + 1), size(n + 1, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        while (p[x] != x) {
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (size[a] < size[b]) swap(a, b);
        p[b] = a; size[a] += size[b];
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<Edge> edges(m);
    for (auto &e : edges) cin >> e.u >> e.v >> e.w;
    vector<int> order(m);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
        if (edges[a].w != edges[b].w) return edges[a].w < edges[b].w;
        return a < b;
    });
    DSU dsu(n);
    vector<vector<pair<int, ll>>> tree(n + 1);
    ll total = 0;
    for (int id : order) {
        const auto &e = edges[id];
        if (dsu.unite(e.u, e.v)) {
            total += e.w;
            tree[e.u].push_back({e.v, e.w});
            tree[e.v].push_back({e.u, e.w});
        }
    }

    int log = 1;
    while ((1LL << log) <= n) ++log;
    vector<vector<int>> up(log, vector<int>(n + 1, 0));
    vector<vector<ll>> mx(log, vector<ll>(n + 1, 0));
    vector<int> depth(n + 1, 0), stack = {1};
    while (!stack.empty()) {
        int v = stack.back(); stack.pop_back();
        for (auto [to, w] : tree[v]) {
            if (to == up[0][v]) continue;
            up[0][to] = v;
            mx[0][to] = w;
            depth[to] = depth[v] + 1;
            stack.push_back(to);
        }
    }
    for (int k = 1; k < log; ++k) {
        for (int v = 1; v <= n; ++v) {
            int mid = up[k - 1][v];
            up[k][v] = up[k - 1][mid];
            mx[k][v] = max(mx[k - 1][v], mx[k - 1][mid]);
        }
    }
    auto path_max = [&](int u, int v) {
        ll best = 0;
        if (depth[u] < depth[v]) swap(u, v);
        int diff = depth[u] - depth[v];
        for (int k = log - 1; k >= 0; --k) {
            if (diff & (1 << k)) {
                best = max(best, mx[k][u]);
                u = up[k][u];
            }
        }
        if (u == v) return best;
        for (int k = log - 1; k >= 0; --k) {
            if (up[k][u] != up[k][v]) {
                best = max(best, max(mx[k][u], mx[k][v]));
                u = up[k][u]; v = up[k][v];
            }
        }
        return max(best, max(mx[0][u], mx[0][v]));
    };
    for (const auto &e : edges)
        cout << total + e.w - path_max(e.u, e.v) << '\n';
}

边界与错误清单

情况 应检查的结果或实现
n=1、m=0 建树与预处理合法，输出为空
输入本来是一棵树 每条边答案都等于树的总权重
同权边与多棵 MST 可以等权替换，不能误判为严格增加
一个端点是另一个的祖先 深度补齐后直接返回，不多算根的虚拟边
两端深度相同但 LCA 更高 同时跳跃后，别遗漏到 LCA 的最后两条边
输入顺序不按权重 排序只用于建树，输出仍遍历原始数组
长链 不使用递归树 DFS 或递归并查集
大权值 W 最多约 2×10¹⁴，int 不能保存总费用

Kruskal 排序 O(m log m)，建树与倍增 O(n log n)，m 次路径查询 O(m log n)，总时间 **O(m log m+(n+m) log n)**，空间 **O(m+n log n)**。m=0 的退化情形也能正确处理。

验证程序位于项目 tests/verify-forced-mst-article.cjs：从本文提取并编译代码，用小图穷举所有生成树独立计算每条边的最优值，再用端点收缩后的 dense Prim 检查更大的随机图，并核验二十万顶点长链与 64 位总权重。它不复用本文的倍增公式作为标准答案。

下一步可回到算法路线对照静态 MST、离线连通性与树上查询：相同的无向图，目标不同，复用的结构也不同。