E. Minimum spanning tree for each edge - 题解

比赛与标签

比赛: Educational Codeforces Round 3 标签: data structures, dfs and similar, dsu, graphs, trees, *2100 难度: *2100

喵喵，这是什么任务呀？ (题目大意)

主人你好呀~！这次的任务是这样的呐：我们拿到一个连通的、带权重的无向图。对于图里的每一条边，我们都想知道，如果必须把这条边包含在一棵生成树里，那么这棵生成树的最小总权重会是多少呢？

简单来说，就是对给定的 m 条边，我们要分别计算 m 个答案，第 i 个答案是“包含第 i 条边的最小生成树”的权重。是不是很有趣的说？

来和咱一起分析吧~喵！ (解题思路)

这个问题看起来好像要我们为每一条边都跑一次算法，但那样肯定会超时的说！所以我们得找个更聪明的办法，喵~

咱们先从最基础的问题想起：如何找到一个图的最小生成树（MST）呢？当然是用 Kruskal算法 啦！它又简单又好用。Kruskal会把所有边按权重从小到大排序，然后用并查集（DSU）一个一个地加边，只要不形成环就行。

好，现在我们用Kruskal算法算出了一个全局的MST，它的总权重是 mst_weight。接下来，我们把所有的边分成两类来考虑：

情况一：这条边本来就在我们的MST里！

如果某条边 e 已经是我们千辛万苦求出来的全局MST的一部分了，那事情就简单多啦！因为全局MST本身就是所有生成树里权重最小的那个，所以包含 e 的最小生成树，不就是这个全局MST自己嘛？所以，对于所有在MST里的边，答案就是 mst_weight。是不是超级简单，喵~

情况二：这条边不在我们的MST里...

这才是挑战所在，主人！假设我们有一条边 e = (u, v)，它的权重是 w，而且它不在我们刚刚计算出的MST里。

如果我们强行要把这条边 e 加入到MST中，会发生什么呢？因为 u 和 v 在MST中本来就是连通的，现在再加一条边 (u, v)，就会在MST里形成一个环！这个环由边 e 和MST中原来连接 u 和 v 的那条唯一路径组成。

一棵树是不能有环的，对吧？所以为了让它重新变回一棵树，我们必须从这个新形成的环里 移除一条边。为了让新生成的树权重尽可能小，我们应该移除哪条边呢？当然是移除环里 权重最大 的那条边啦！

所以，对于一条不在MST里的边 e(u, v)，包含它的最小生成树的权重就是： 新MST权重 = mst_weight + w - (MST上u到v路径中的最大边权)

那么问题来了：如何快速查询MST上任意两点路径的最大边权呢？

这可是个经典问题！我们可以用 倍增法（Binary Lifting） 来高效解决。这个方法通常也用来求LCA（最近公共祖先）。

预处理：
- 首先，我们在求出的MST上进行一次DFS（深度优先搜索），计算出每个节点的深度 depth、它的父节点 parent[i][0]，以及连接它和父节点的边的权重 max_w[i][0]。
- 然后，我们用动态规划的思想来填充倍增数组。parent[i][j] 表示节点 i 的第 2^j 个祖先，max_w[i][j] 表示从 i 向上跳 2^j 步路径上的最大边权。递推关系如下：
  - parent[i][j] = parent[parent[i][j-1]][j-1]
  - max_w[i][j] = max(max_w[i][j-1], max_w[parent[i][j-1]][j-1])
查询：
- 当我们要查询 u 和 v 之间路径的最大边权时，我们先把深度较大的那个节点（比如 u）向上跳，直到它和 v 的深度相同。在这个过程中，我们不断更新遇到的最大边权。
- 然后，我们让 u 和 v 一起向上跳，直到它们的父节点相同（这个父节点就是它们的LCA）。同样，在跳跃的过程中记录遇到的最大边权。
- 最后，不要忘了算上 u 和 v 连接到它们LCA的那两条边的权重。把所有记录到的最大值取最大，就是我们想要的答案啦！

总结一下我们的完整计划：

用Kruskal算法求出全局MST和它的总权重 mst_weight。
在MST上进行DFS和倍增预处理，建立可以快速查询路径最大边权的数据结构。
遍历所有 m 条原始边：
- 如果边在MST里，答案就是 mst_weight。
- 如果边不在MST里，就用倍增法查询它连接的两个顶点在MST上路径的最大边权，然后用上面的公式计算出答案。

这样，我们就能高效地解决所有查询了，喵~

看咱的代码魔法！✨ (代码实现)

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

// 为数组大小设置一些常量，是个好习惯喵~
const int MAXN = 200005;
const int LOGN = 18; // log2(200005) 约等于 17.6，所以18很安全

// 边的结构体，不仅存了u,v,w，还存了它最初的id，方便最后按顺序输出
struct Edge {
    int u, v, w, id;
};

// 排序函数，为了Kruskal算法，我们要按权重从小到大排序
bool compareEdges(const Edge& a, const Edge& b) {
    return a.w < b.w;
}

// 可爱又高效的并查集（DSU）
struct DSU {
    std::vector<int> parent;
    DSU(int n) {
        parent.resize(n + 1);
        std::iota(parent.begin(), parent.end(), 0); // 每个节点的父亲一开始都是自己
    }

    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]); // 路径压缩，超重要的优化！
    }

    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j; // 合并两个集合
        }
    }
};

// 全局变量，用来存MST的邻接表和倍增用的数组
std::vector<std::pair<int, int>> adj[MAXN];
int depth[MAXN];
int parent[MAXN][LOGN];
int max_w[MAXN][LOGN];

// 在MST上做DFS，为倍增做准备
void dfs(int u, int p, int d, int w_edge) {
    depth[u] = d;
    parent[u][0] = p; // u的2^0=1个祖先就是它的父亲p
    max_w[u][0] = w_edge; // u到父亲p的边权
    for (const auto& edge : adj[u]) {
        int v = edge.first;
        int w = edge.second;
        if (v != p) { // 防止往回走
            dfs(v, u, d + 1, w);
        }
    }
}

// 预处理倍增数组，O(N log N) 的魔法！
void precompute_lca(int n) {
    for (int j = 1; j < LOGN; ++j) {
        for (int i = 1; i <= n; ++i) {
            if (parent[i][j - 1] != 0) { // 如果i的第2^(j-1)个祖先存在
                // i的第2^j个祖先，是它第2^(j-1)个祖先的第2^(j-1)个祖先
                parent[i][j] = parent[parent[i][j - 1]][j - 1];
                // i到第2^j个祖先路径上的最大边权
                max_w[i][j] = std::max(max_w[i][j - 1], max_w[parent[i][j - 1]][j - 1]);
            }
        }
    }
}

// 查询u和v在MST上路径的最大边权
int query_max_path(int u, int v) {
    int res = 0;
    if (depth[u] < depth[v]) {
        std::swap(u, v); // 保证u是更深的那个节点
    }

    // 第一步：把u跳到和v一样深
    for (int j = LOGN - 1; j >= 0; --j) {
        if (depth[u] - (1 << j) >= depth[v]) {
            res = std::max(res, max_w[u][j]);
            u = parent[u][j];
        }
    }

    if (u == v) {
        return res; // 如果u就是v的祖先，那我们已经找到了
    }

    // 第二步：让u和v一起往上跳，直到它们的父节点是同一个（即LCA）
    for (int j = LOGN - 1; j >= 0; --j) {
        if (parent[u][j] != 0 && parent[u][j] != parent[v][j]) {
            res = std::max(res, max_w[u][j]);
            res = std::max(res, max_w[v][j]);
            u = parent[u][j];
            v = parent[v][j];
        }
    }
    
    // 最后一步：u和v的父节点就是LCA了，别忘了它们俩到LCA的最后两条边
    res = std::max(res, max_w[u][0]);
    res = std::max(res, max_w[v][0]);

    return res;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    std::cin >> n >> m;

    std::vector<Edge> edges(m);
    for (int i = 0; i < m; ++i) {
        std::cin >> edges[i].u >> edges[i].v >> edges[i].w;
        edges[i].id = i;
    }

    // 用Kruskal算法构建全局MST
    std::sort(edges.begin(), edges.end(), compareEdges);

    DSU dsu(n);
    long long mst_weight = 0;
    std::vector<bool> in_mst(m, false);
    for (const auto& edge : edges) {
        if (dsu.find(edge.u) != dsu.find(edge.v)) {
            dsu.unite(edge.u, edge.v);
            mst_weight += edge.w;
            in_mst[edge.id] = true; // 标记这条边在MST里
            adj[edge.u].push_back({edge.v, edge.w});
            adj[edge.v].push_back({edge.u, edge.w});
        }
    }

    // 图是连通的，所以从任意节点（比如1）开始DFS，构建倍增所需的数据
    dfs(1, 0, 0, 0); // 根是1，父节点设为0（哨兵），深度0，到父节点边权0
    precompute_lca(n);

    // 计算每条边的答案
    std::vector<long long> ans(m);
    for (const auto& edge : edges) {
        if (in_mst[edge.id]) {
            // 情况一：边在MST里，答案就是MST的总权重
            ans[edge.id] = mst_weight;
        } else {
            // 情况二：边不在MST里，用公式计算
            int max_path_w = query_max_path(edge.u, edge.v);
            ans[edge.id] = mst_weight - max_path_w + edge.w;
        }
    }

    // 按原始顺序输出答案
    for (int i = 0; i < m; ++i) {
        std::cout << ans[i] << "\n";
    }

    return 0;
}

跑得快不快呀？ (复杂度分析)

时间复杂度: O(M log M + N log N) 的说。
- std::sort 对 M 条边排序，是 O(M log M)。
- Kruskal算法用并查集，复杂度是 O(M * α(N))，其中 α(N) 是反阿克曼函数，增长非常慢，可以近似看作常数。
- 在MST上DFS是 O(N)。
- 倍增预处理是 O(N log N)。
- 最后对 M 条边进行查询，对于不在MST里的边，每次查询是 O(log N)，总共是 O(M log N)。
- 综合起来，瓶颈在于排序和查询，所以总时间复杂度是 O(M log M + M log N)。因为 log M 和 log N 通常在一个数量级，可以写成 O(M log M) 或 O(M log N)。
空间复杂度: O(N log N + M) 的说。
- 存储 M 条边需要 O(M) 空间。
- 并查集需要 O(N) 空间。
- MST的邻接表需要 O(N) 空间。
- 最大的开销来自倍增的数组 parent 和 max_w，它们的大小都是 N * LOGN，所以是 O(N log N)。
- 因此总空间复杂度是 O(N log N + M)。

这次学到了什么喵？ (知识点与总结)

这道题真是一次精彩的算法组合拳练习，喵~

MST 的性质: 这道题的核心是对MST性质的深刻理解。特别是 环路性质：向一棵生成树中添加任意一条非树边，都会形成一个唯一的环。要得到新的生成树，必须从环中去掉一条边。为了让新树权值最小，我们去掉环中最重的边。
算法组合: 我们把 Kruskal (贪心) + DSU (并查集) + Binary Lifting (倍增) 这三个强大的工具组合在了一起，完美地解决了问题。这告诉我们，很多复杂问题都是由一些经典算法模块构成的，学好基础很重要！
倍增法的泛用性: 倍增法不仅能求LCA，还能查询路径上的各种可合并信息（比如最大值、最小值、和等）。只要信息满足结合律，就可以用倍增来加速查询。
离线处理思想: 我们不是对每条边都独立计算，而是先建立一个全局的MST和倍增结构，然后利用这个结构一次性回答所有查询。这种先预处理再集中回答的“离线”思想在竞赛中非常常用。

希望这篇题解能帮到你哦，主人！继续加油，算法的世界还有更多好玩的东西等着我们去探索呢，喵~！

E. Minimum spanning tree for each edge - 题解 ​

比赛与标签 ​

喵喵，这是什么任务呀？ (题目大意) ​

来和咱一起分析吧~喵！ (解题思路) ​

情况一：这条边本来就在我们的MST里！ ​

情况二：这条边不在我们的MST里... ​

那么问题来了：如何快速查询MST上任意两点路径的最大边权呢？ ​

看咱的代码魔法！✨ (代码实现) ​

跑得快不快呀？ (复杂度分析) ​

这次学到了什么喵？ (知识点与总结) ​