次小生成树

迟到的讲解（还不会来找我，我在线

悟空：我看你可邢。

前置知识

• 倍增、LCA ： 倍增LCA

• MST（最小生成树） ： Kruskal算法

什么是次小生成树？

顾名思义，就是比最小生成树大一点的生成树。

非严格次小生成树

在无向图中，边权和最小的满足边权和 大于等于 最小生成树边权和的生成树

👀 换句话说，非严格次小生成树权值和可以等于最小生成树。

严格次小生成树

在无向图中，边权和最小的满足边权和 严格大于 最小生成树边权和的生成树

求次小生成树

用相对基础的 Kruskal+倍增+LCA 算法组合。剧透

• 注意到最小生成树和次小生成树的边应该有很多都是一样的，只有部分边不同

顺理成章的，我们就可以先找出一个最小生成树，在这棵最小生成树的基础上进行修改，即可。（轻轻松松

具体地说就是在非最小生成树上边中按照边权从小到大枚举每一条边，把枚举到的边加入最小生成树中，这时最小生成树上会出现一个环，我们把这个环上的最大边断开就可以得到非严格最小生成树了. . . . . . （证明是什么？能吃吗？）

• 算法步骤

（最小生成树 -> 次小生成树）

1. 首先Kruskal求出MST，顺便建起邻接表

2. 枚举每条MST之外的边，当连上之后会出现环

3. 找到环中除加上的边之外权值最大的边

4. 删除该边之后，变成另一个树，为次小生成树树

非严格、严格次小生成树区别

非严格次小生成树通过最小生成树算法基础上删除最大环边来实现。
严格次小生成树则需要额外维护树上的次大值！

• 总结，非严格次小生成树要维护最大值；严格次小生成树要维护最大值和次大值。

好了，问题转换成，怎么求树上任意两点间的最短路径上的最大边权？

容易想到一种朴素的做法，通过这个树初始化某点到其他点的路径中最大边、（次大边）。 $(n^2)$
遍历所有未在树中的边（u–>v），看是否大于u到v的边的最大值， 若大于那么可以替换这条边，（若不大于那就再判断是否大于次值），若大于同理进行替换。但是初始化复杂度为$(n^2)$，舍弃。

倍增LCA

• 可以发现添加的边所连接的两个节点到他们在MST上的LCA的两条路径就会组成一个环，我们需要的就是这两条路径上的最大边权，寻找边权可以在利用倍增求LCA时顺便维护。

当然求LCA的算法有很多，比如tarjan的离线算法O(n+q)，RMQ±1
倍增法比较方便O(N+NlogN)，所以考虑使用倍增LCA
倍增LCA做法其实核心就是st (也就是RMQ)

根据$f[x][k] = f[f[x][k-1]][k-1]$的递推，

可以类似求出$d[x][k] = max(d[x][k - 1], d[f[x][k-1]][k - 1])$

查询的时候，查询x–>y中路径的最大值、（次大值）。

那么可以在lca的查询中，查询x->lca那一段中的所有最大、次大，y到lca中所有的最大、次大，最后从这些最大、次大里面选出最大、次大值即可。

$复杂度为O(MlogM)$

模板题

这些重要模板题必须练习，好好消化，建议自己画图。初学可以再借助题解消化（学长们的题解真的又多详细

practice make perfect

• O(n^2)暴力次小生成树：1148. 秘密的牛奶运输 （算法提高课）

• 倍增LCA次小生成树：356. 次小生成树 （算法禁赛进阶指南）

话外音

$$ 悟空：俺老孙还会树剖、LCT求严格次小生成树！！！$$
$$ 杨戬：你再装b，写得时候用 Kruskal+倍增+LCA，常见，方便！$$

举手之劳，就点个赞再走呗 ε==(づ′▽`)づ
求支持，跪谢！

鸣谢：@Conan15