次小生成树.md

###次小生成树
````
定义:给定一个带权的图,把图的所有生成树按权值从小到大排序
第二小的称为次小生成树

则显然第一种定义,最小生成树和次小生成树的权值和可能相等

第二种定义:次小生成树严格大于最小生成树的权值和
次小生成树是权值和大于最小生成树的那个最小的那个生成树

两种写法相似

方法1:求最小生成树,再枚举删去最小生成树中的边求解
O(mlog m)+O(nm)  无法求严格次小生成树

方法2:先求最小生成树,依次枚举非树边,可以求出严格最小生成树
然后将该边加入树,同时从树中去掉一条边,使得最终的图仍然是树,则一定可以求出次小生成树
预处理,以任意节点为根,(BFS/DFS)枚举到任何点的最大边权O(n^2), 最终O(n^2+m+n^2+mlogn)
sum+w新-w树
LCA预处理O(mlogn+m+n^2+mlogn)
存在一棵次小生成树和最小生成树相差一条边