首先我们要明确：次小生成树分为两种，一种是非严格次小生成树，一种是严格次小生成树。

非严格次小生成树的边权和大于等于最小生成树的边权和，严格次小生成树边权和一定大于最小生成树的边权和



方法一：（适用于非严格次小生成树）先求最小生成树，再枚举删去每条最小生成树的边求解

时间复杂度O(nm)



方法二：（非严格次小生成树和严格次小生成树均适用）先求最小生成树，再枚举在最小生成树中增加该非树边，

再删去形成环上的最大的一条最小生成树的边（可以通过预处理解决，dfs其他方法），即res+非树边-最大的树边

如果求的是严格次小生成树，需要限制非树边大于树边，如果该非树边等于最大树边，则尝试替换次大值。

如果非树边大于次大值，则尝试特换次大值

如果求的是非严格次小生成树，则不需要该限制条件

时间复杂度O(n^2)



在第二种方法中

通过反证法可证，一定存在一个次小生成树只与最小生成树只存在一条边不同，

无论是非严格次小生成树还是次小生成树均是如此。



通过比较我们可以知道第二种方法比较灵活，即可以求严格次小生成树，也可以求非严格次小生成树。

而第一种方法只适用于求非严格次小生成树，因此第二种方法应用更为广泛