最小生成树问题的增量构造与在线最小生成树（Incremental MST）问题

题目描述

假设你有一个初始为空的无向连通图，图中的顶点集合固定为 V（顶点数为 n），但边是逐步出现的——初始时图中没有任何边，之后每次添加一条带权边。每添加一条边后，你都需要回答当前图的最小生成树（MST）的总权重是多少。这个问题通常称为增量/在线最小生成树（Incremental MST）问题。

输入：

• 顶点数 n
• 一系列操作，每个操作为“添加一条连接顶点 u 和 v、权重为 w 的边”，操作总数记为 m。

目标：

• 对每个添加操作，输出当前图的最小生成树的总权重。

约束：

• 2 ≤ n ≤ 10^5
• 1 ≤ m ≤ 2 × 10^5
• 权重 w 为整数（可能为负）
• 图始终是连通的（即 m 足够大，保证最终图连通）

解题思路

如果每次添加边后都重新运行 Kruskal 或 Prim 算法，复杂度为 O(m² log n)，显然不可接受。我们需要利用MST 的动态性质：当加入一条新边 e = (u, v, w) 时，它可能会替换掉当前 MST 中 u 到 v 路径上权重最大的一条边（如果那条边的权重大于 w）。这实际上是MST 的最优子结构性质的一种动态表现。

核心观察（MST 替换边性质）：
设 T 是当前图的最小生成树，加入新边 e = (u, v, w)。则：

1. 如果 w 小于 T 中 u 到 v 路径上的最大边权重 max_edge(u, v)，那么用 e 替换掉那条最大边，可以得到新的最小生成树，新 MST 的权重变化为 w − max_edge(u, v)。
2. 如果 w ≥ max_edge(u, v)，则 MST 不变。

因此，我们需要一种数据结构，能够：

• 维护当前的 MST（以树的形式）
• 快速查询树上任意两点路径上的最大边权重
• 支持动态替换树边（删除一条树边，加入一条新边，并更新树结构）

逐步详解

步骤1：维护动态树

查询树上路径最大边权，并支持边替换，这正好是动态树（Link-Cut Tree, LCT） 的经典应用。LCT 可以在 O(log n) 时间内完成：

• link(u, v, w)：连接 u 和 v（加入树边）
• cut(u, v)：删除树边
• query_max(u, v)：查询 u 到 v 路径上的最大边权重，并返回最大值对应的边标识

但注意：LCT 通常维护点权，我们可以将边权转化为“点权”——常用技巧是将边转化为一个新点，但这里采用另一种常见方法：将边 (u, v, w) 表示为连接 u 和 v 的一条边，在 LCT 中，我们将这条边的权重视为连接 u 和 v 的这条“边”所关联的“点”的权值（实际上在 LCT 的实现中，我们为每条边创建一个额外的节点，这个节点的权值就是 w，然后将这个节点分别与 u 和 v 连接，这样查询路径最大值时就会包含这个“边节点”的权值）。

步骤2：算法流程

1. 初始化：

   • 初始时 MST 为空，总权重 sum = 0。
   • 用 LCT 维护一个森林（初始时每个顶点单独一棵树，无边）。
   • 顶点编号 1~n，边加入时我们为每条边分配一个全局唯一 ID，并在 LCT 中创建一个“边节点”（节点编号从 n+1 到 n+m），其权值为边权 w。

2. 处理一次加边操作 (u, v, w)：

   • 如果当前 u 和 v 在 LCT 中不连通（即它们不在同一棵树中），则直接加入这条边不会形成环，因此直接将此边加入 MST：
     • 在 LCT 中创建边节点 e_id（权值 w）。
     • 执行 link(u, e_id) 和 link(e_id, v)。
     • sum += w。
   • 如果 u 和 v 已经连通（在同一棵树中），则：
     • 查询 T 中 u 到 v 路径上的最大边权重 max_w 以及该最大边对应的边节点 id max_e_id。
     • 如果 w < max_w：
       • 从 MST 中删除 max_e_id 这条边：执行 cut(max_e_id, 其一个端点) 和 cut(max_e_id, 另一个端点)。
       • 将新边加入 MST：创建新边节点 new_e_id，执行 link(u, new_e_id) 和 link(new_e_id, v)。
       • sum += w − max_w。
     • 如果 w ≥ max_w：MST 不变，新边直接丢弃（不加入 LCT 的树结构，但可以保留边节点记录，只是不 link 到树上）。

3. 输出当前 sum。

注意：即使 w ≥ max_w，我们依然可以创建边节点（只是不 link），但为了节省内存，可以只在实际加入 MST 时才创建边节点。不过，由于 LCT 需要预先分配节点，通常我们会为每条输入的边预分配一个节点编号。

关键细节

1. LCT 中的边权转点权

在 LCT 的每个节点上维护：

• 该节点的权值（对于真实顶点，权值为 -∞ 或一个极小值，因为顶点不参与最大边权比较；对于边节点，权值为边权 w）。
• 子树中最大权值及所在节点编号（用于查询路径最大值）。

在 splay 和 push_up 操作中更新这些信息。

2. 边的删除

当我们需要从 MST 中删除一条边时，该边对应的边节点在 LCT 中连接了两个顶点。我们只需对该边节点执行两次 cut 操作，切断它与两个端点的连接。

3. 时间复杂度

• 每次加边操作：O(log n)（LCT 操作复杂度均摊 O(log n)）。
• 总复杂度：O(m log n)，可处理 n, m 在 10^5 级别。

举例说明

假设 n=4，初始 MST 权重=0，无边。

1. 加边 (1,2,3)：1 和 2 不连通，直接加入 MST，sum=3。
2. 加边 (2,3,4)：2 和 3 不连通，直接加入，sum=7。
3. 加边 (3,4,2)：3 和 4 不连通，直接加入，sum=9。
   MST 现在是 1-2-3-4。
4. 加边 (1,4,6)：1 和 4 已连通，查询路径 1→2→3→4 上最大边权：max_w=4（边(2,3)）。因为 6≥4，MST 不变，sum=9。
5. 加边 (2,4,1)：2 和 4 已连通，查询路径 2→3→4 上最大边权：max_w=4（边(2,3)）。因为 1<4，删除边(2,3)，加入边(2,4)：
   • 删除(2,3)：sum -= 4 → sum=5。
   • 加入(2,4)：sum += 1 → sum=6。
     新 MST：1-2-4-3，权重 3+1+2=6。

每次操作后输出当前 sum。

伪代码

初始化 LCT，节点 1..n 权值为 -inf
sum = 0
边节点编号 e_id = n+1

for 每条新边 (u, v, w):
    if not connected(u, v):  # 不连通
        创建边节点 e_id，权值 w
        link(u, e_id)
        link(e_id, v)
        sum += w
        e_id++
    else:
        max_w, max_e_id = query_max(u, v)
        if w < max_w:
            # 删除最大边
            cut(max_e_id, 其邻接点1)
            cut(max_e_id, 其邻接点2)
            sum -= max_w
            # 加入新边
            创建边节点 e_id，权值 w
            link(u, e_id)
            link(e_id, v)
            sum += w
            e_id++
   输出 sum

总结

• 增量 MST 问题的核心是利用 MST 的替换边性质，在加边时只替换路径上的最大边。
• 需要一种数据结构维护树上路径最大值及动态加边/删边，Link-Cut Tree 是理想选择。
• 每条边转化为一个 LCT 中的“边节点”，权值为边权，从而用 LCT 的点权维护边权最大值。
• 总时间复杂度 O(m log n)，空间 O(n+m)。