# MST 替换边、强制选边与边的三分类

## 本节目标

学完后，你应能利用“非树边加入后形成唯一环”计算强制选边代价，并在 Kruskal 同权批次中判断一条边属于所有、至少一棵或不属于任何 MST。

## 前置知识与课前自测

前置：Kruskal、LCA/倍增、桥。

1. 向一棵生成树加入非树边 $(u,v)$ 后形成几个环？
2. 强制保留该边时，应从环上删最轻边还是最重边？
3. 同权边为什么不能按任意顺序立即并查集合并后再分类？

<details><summary>自测答案</summary>

1. 唯一一个，由该边和树上 $u-v$ 路径组成。
2. 删树路径上的最重边，得到包含新边的最小权生成树。
3. 先处理的同权边会人为改变后处理边的连通性，把本可互换的边误标成无用。

</details>

## 问题动机与核心知识

固定一棵 MST $T$，加入非树边 $e=(u,v,w)$。任一包含 $e$ 的生成树必须在它形成的环上删一条边；为最小化新树权，应删路径最大边 $M$：

$$
W_e=W(T)+w-M.
$$

若 $w=M$，存在等权替换，说明 MST 可能不唯一。这个结论把“每条边强制选入”转为树上路径最大值查询。

另一类问题要求不先固定某棵 MST，而直接分类全部边。处理权值 $w$ 前，Kruskal 已由更小权边形成若干分量：

- 两端已在同一分量：加入必成环，不属于任何 MST；
- 两端不同：在以这些分量为点、当前同权边为边的临时多重图中，它至少属于一棵 MST；
- 若它还是临时图的桥，则连接两侧没有同权替代，属于每棵 MST。

## 实现指南

- 路径最大值用二进制提升（binary lifting），预处理 $O(n\log n)$、查询 $O(\log n)$。
- 同权分类必须分成“查询当前 DSU—临时图判桥—整批 union”三阶段。
- 临时图可能出现平行边，即使原图无重边，因为多个原点可能压到同一对 DSU 分量；桥算法必须按边编号跳父边。

## 精选例题 1：Minimum spanning tree for each edge

### 来源信息与题意

- VJudge：[CodeForces-609E Minimum spanning tree for each edge](https://vjudge.net/problem/CodeForces-609E)
- 原题：[Educational Codeforces Round 3](https://codeforces.com/problemset/problem/609/E)
- 难度：2100；考点：MST、树上倍增最大值、强制选边

连通简单无向图有 $n,m\le2\times10^5$，边权至 $10^9$。对每条边，求必须包含它的最小生成树权值。

<details><summary>Hint 1</summary>先任选一棵 MST 并记录总权。</details>
<details><summary>Hint 2</summary>非树边加入后，只需删除其两个端点在 MST 路径上的最大权边。</details>
<details><summary>Hint 3</summary>树边答案就是原 MST 总权；路径最大值用 LCA 倍增。</details>

### Observations、Editorial 与证明

Kruskal 得到 MST。对非树边 $e$，加入后产生唯一环；任一包含 $e$ 的树需删环上一条树边，删最大边最优。设存在更优的包含 $e$ 的生成树 $T'$，把 $e$ 从 $T'$ 删掉得到一个割；原 MST 必有一条边 $f$ 跨越该割，且 $w(f)\le w(e)$（否则把 $f$ 换入 $T$ 可改进 MST）。用 $f$ 替换 $T'$ 中的某条边得到的生成树仍不差于 $T'$，故 $T'$ 不是更优者，删路径最大边即最优。

总复杂度 $O((n+m)\log n)$，答案用 `long long`。

### 核心伪代码与参考实现附件

```text
T, total = Kruskal_MST(graph)
preprocess binary lifting for maximum edge on every tree path
for edge e=(u,v,w):
    if e belongs to T: answer[e] = total
    else: answer[e] = total + w - maximum_on_tree_path(u,v)
```

完整 GNU C++17 参考实现见附件：[CodeForces-609E.cpp](../../参考实现/06-最小与最大生成树/CodeForces-609E.cpp)

### 复盘与变式

若问强制删除一条 MST 边后的最优值，需要找所有跨越该树边割的非树边最小权，通常用树上路径区间取最小的离线更新。

## 精选例题 2：Edges in MST

### 来源信息与题意

- VJudge：[CodeForces-160D Edges in MST](https://vjudge.net/problem/CodeForces-160D)
- 原题：[Codeforces Round 111 (Div. 2)](https://codeforces.com/problemset/problem/160/D)
- 难度：2300；考点：同权批次、DSU 缩点、临时图判桥

给连通简单带权无向图，$2\le n\le10^5$，逐边输出：属于每棵 MST（`any`）、至少一棵（`at least one`）或不属于任何 MST（`none`）。

<details><summary>Hint 1</summary>按权分组；处理权 $w$ 时，DSU 只能包含严格小于 $w$ 的边。</details>
<details><summary>Hint 2</summary>两端已经同组的边是 `none`；其余边在当前 DSU 分量构成的临时图中竞争。</details>
<details><summary>Hint 3</summary>临时图中的桥无法由另一组同权边替代，是 `any`；其他候选为 `at least one`。</details>
<details><summary>Hint 4</summary>分类结束后再把整组边 union，为下一权值做准备。</details>

### Observations、Editorial 与证明

Kruskal 在权 $w$ 前的 DSU 分量由所有更轻边强制形成。组内一条边若两端同分量，加入会在更轻边上成环，必不入 MST。否则，任何 MST 在临时图每个连通块中选择一棵生成森林；非桥可通过交换进入某棵森林，桥则是连接其两侧的唯一同权选择，所有森林都必须包含。

每条边只进入一次临时图，桥判定总规模线性，加排序总复杂度 $O(m\log m+n\alpha(n))$。

### 核心伪代码与参考实现附件

```text
sort edges into equal-weight groups; DSU contains only lighter edges
for each group:
    edges already inside one DSU component are 'none'
    contract DSU roots and build a temporary multigraph from remaining edges
    temporary bridges are 'any'; other remaining edges are 'at least one'
    union all group edges in the global DSU
```

完整 GNU C++17 参考实现见附件：[CodeForces-160D.cpp](../../参考实现/06-最小与最大生成树/CodeForces-160D.cpp)

### 复盘与变式

若只问 MST 是否唯一，只要某个同权临时图存在非桥候选可交换即可判否；也可在固定 MST 上检查非树边权是否等于树路径最大值。

## 扩展与联系

- 次小生成树用同一替换公式：在所有非树边中取 $w>max$ 的最小 $w-max$，再加上 $W$ 即为次小生成树权。
- 最大生成树把路径最大替换为路径最小，比较方向反转。
- `CodeForces-1108F MST Unification` 本质是在同权临时图中消除可交换选择；可作为本节迁移训练。

## 总结与自检

1. 强制选非树边的替换公式为何删路径最大边？
2. 正权/非负权是否影响这个替换结论？
3. 边分类为何必须按同权批次？
4. 临时图桥为何对应 `any`？平行边如何影响桥？

## 课后训练建议

先用枚举全部生成树对拍两份实现。第一题重点验证非树边公式；第二题构造同权三角形、同权平行缩点边和严格最轻割边。完成后做 `MST Unification`，只在无法建立“同权临时图”时回看 Hint。