我自己想的有关次小生成树定理的证明，希望能稍微帮到有需要的人

public class Acwing1148￥ {
    /*
    这个要求是次小生成树，而且是严格小的次小生成树
    其实思路还是挺简单的，首先就是把最小生成树给求出来，记录下来。
    然后枚举非树边a，加入到树中，再去掉树中的一条边b
    T + a - b如果还是一棵生成树，则这就是一次可行变换，
    T进行一次可行变换之后得到的所有生成树称为T的临集
    定理：次小生成树一定在临集里面
    这个定理怎么证明呢？
    就是一定存在一棵次小生成树，他跟最小生成树只有一条边不同
    我发现我应该先证明Kruskal算法或者Prim算法的正确性
    先证明Kruskal算法的正确性。
    这个我是不是证明过了么。首先我们证明，假设e[0]是整张图里面最短的边，那么至少有一个最小生成树会包含e这条边
    反证法嘛，如果所有的最小生成树全都不包含这条边，假设e[0]的两个端点是a[0]和b[0]，那么任取一棵最小生成树
    a[0]跟b[0]之间肯定通过某条路径P[0]连通在一起，就在P[0]上面随便找一条边扔掉，把e[0]加进来，就可以得到一棵包含e[0]的最小生成树了吧，矛盾，于是肯定有至少一棵最小生成树是包含e[0]的
    那么我们就可以把最小生成树的集合拿过来，只取其中包含e[0]的那些，这个集合记为S[1]
    然后我们再来，假设Kruskal算法下一步要延展的边是e[1]，它的2个端点是a[1]和b[1]，我们可以做同样的操作吧，假设S[1]里面所有的树全都不包含e[1]，随便取一棵T[1]
    在T[1]里面的a[1]和b[1]也是通过某条路径P[1]连在一起的，那问题来了，P[1]上面的边有没有可能全都严格地比e[1]要短？
    应该是不可能的，因为T[1]里面也有e[0]，然后e[1]的定义是不会跟e[0]形成环的边里面最短的那个，而T[1]里面也没有环，于是我们知道P[1]上的边全都是不会跟e[0]形成环的边
    因此他们不会比e[1]更短的，于是我们可以选中一条去掉然后把e[1]加进来，就可以得到一个包含e[1]的最小生成树了，产生矛盾
    就这样一直做下去，把S[1]里面包含e[1]的抠出来变成S[2]，一直下去就可以得到，Kruskal算法得到的确实就是最小生成树了

    假设G的最小生成树是T*，然后在T*之外取一条边e加到T*里面，再去掉T*中的某一条边，进行一次这样的操作能得到的生成树集合称为T的邻集
    我们要证明，G的次小生成树一定在T的邻集里。
    直观上讲就是G的次小生成树跟最小生成树最多只差一条边。
    我们先证明对于非严格次小生成树是成立的。所谓非严格次小生成树就是这个集合里面S = {T| w(T) >= w(T*) and T != T*}里面权值最小的那个
    用反证法，假设S里面所有的T跟T*之间都至少差2次操作，那么我们知道T*是根据Kruskal算法生成的，每次添加的边肯定是从小到大排序的，我们可以排成
    e[1], e[2].... e[n - 1]，总共n个点嘛，生成一棵树只要n - 1条边就好
    那么肯定存在这样的k such that e[1 ~ k - 1] belongs to T[0] and e[k] not belongs to T[0]
    你大不了一条边一条边看过来它是否属于T嘛，当然也有可能k = 1
    那么e[k]的2个端点是a[k], b[k]的话，我们知道在T[0]里面a[k]和b[k]也是通过某条路径连在一起的
    假设是a[k] -- s[1] -- ... s[t] -- b[k]，我们可以先假设t = 2，看看是个什么情况
    a[k] -- s[1] -- s[2] -- b[k]这是在T里面的路径
    那么我们来看a[k] -- s[1]这条边有没有在e[1] ~ e[k - 1]里面呢？如果他在的话，那么s[1] -- s[2]和s[2] -- b[k]就肯定不能同时在e[1] ~ e[k - 1]里面，否则的话
    Kruskal算法没理由接下来会选择a[k] -- b[k]这条边，会形成环的呀。于是我们知道了，那么s[1] -- s[2]和s[2] -- b[k]这2条边是里面至少有一条 >= a[k] -- b[k]的
    因为我们的假设是a[k] -- s[1] 在e[1] ~ e[k - 1]里面嘛，如果s[2] -- b[k] < a[k] -- b[k] and s[1] -- s[2] < a[k] -- b[k]的话Kruskal算法接下来也不应该选a[k] -- b[k]这条边
    所以我们得到，这个时候你把s[1] -- s[2]和s[2] -- b[k]里面不属于e[1] ~ e[k - 1]的边去掉，然后把a[k] -- b[k]加上去，就可以得到一个次小生成树T[1]了吧。
    因为T[1]是生成树，所以它权值必定>= T*的
    实际上你这样操作一次得到的T[1]说不定都直接是T*了，如果不是的话就继续这样的操作，上面t = 2好像已经足够说明情况了，完全可以拿t = 3再看一下是什么情况
    这样一直操作下去就会发现是距离T*越来越近的，这是因为你对T[1]求一下那个e[1 ~ k - 1]属于T[1]而e[k]不属于T[1]
    这个T[1]的k跟T[0]的k相比则何如呢？
    为了区分我们设置一个是k[1]一个是k[0]吧，我们可以发现，T[0]里面e[1 ~ k[0] - 1]全都被保留下来了，你看看上面操作中，去掉的边根本不是e[1 ~ k[0] - 1]里面的
    然后还多加了一条e[k[0]]进来，所以其实k[1] >= k[0] + 1的
    正因如此我才说，这样的操作会越来越靠近T*的，直到有一天我发现，我操作之前不是T*，操作之后就是T*了，这个时候就可以证明，非严格次小生成树里面至少有一棵是可以通过T*操作一次得到的

    还没完，我们还得证明，严格次小生成树里面是不是也是至少有一棵跟T*的差别只有一次操作呢？
    严格次小生成树的集合就是S = {T | w(T) > w(T*)}严格次小生成树就是S里面w最小的那个
    我们还是用反证法吧，假设所有的严格次小生成树都要至少经过2次操作才能变成T*，那我们任意取一个T[0]，严格次小生成树
    同样地我们把e[1] ... e[n - 1]列出来，肯定可以找到e[1] ~ e[k - 1] 属于T[0]而e[k]不属于T[0]
    e[k]的2个端点是(a[k], b[k]) 然后在T[0]里面a[k] -- s[1] -- s[2] -- b[k]还是用中间插入2个来说明问题
    那同理我们知道，(a[k], s[1]), (s[1], s[2]), (s[2], b[k])不能同时属于e[1 ~ k - 1]否则跟Kruskal选的都是不产生环的最短边矛盾
    那就假设(s[1], s[2]) 不属于e[1 ~ k - 1]，当然了这并不意味着(a[k], s[1]), (s[2], b[k])一定会属于e[1 ~ k - 1]哈
    那我们知道(s[1], s[2])这条边肯定是>= e[k]的，如果是严格大的，那我们不能换，因为你一换的话可能把T[0]这个次小生成树变成最小生成树了
    如果是相等话那我们可以换，这个时候就回归到上面那个非严格的情况了
    所以我们最关键是处理(s[1], s[2]) > e[k]的情况，这个时候你好像不能动它，我们继续找下一个能动的位置，能动的位置至少2个的嘛。
    你会发现，能动的位置里面，是不等号的肯定只会有1个位置，因为如果有2个话我可以把其中的一个给动了，就可以得到一个比次小生成树更小的，然后比最小生成树大的了，那这个才应该是次小生成树了吧。
    于是我们就看到了，所有能动的位置肯定只有1个会是不等号，那我们先把等号的全都给动了，最后留下的应该就是，跟T*只差一个操作的次小生成树了吧，那个操作对应的就是那个不能动的位置。
    当然了我上面的这个证明还是有点不太严格，但是至少对我自己而言已经加深了很多理解了，我不想再深究了。2021年6月4日21:17:45
     */
}