Part 2：求解（严格）次小生成树

传送门：【模板】严格次小生成树

什么是次小生成树

字面意思来讲，次小生成树就是除了最小生成树之外最小的那棵生成树

那么为什么把“严格”加了个括号呢？因为它并不严格（废话）

如果最小生成树选择的边集是\(E_M\)，严格次小生成树选择的边集是\(E_S\)，那么需要满足：\((value(e)\)表示边\(e\)的权值\()\)

\(\sum_{e \in E_M}value(e)<\sum_{e \in E_S}value(e)\)

显然这个公式它比较恶心，简单来说，就是次小生成树的大小必须严格小于最小生成树的大小

如果我们只是在最小生成树上更换了边，但是总的生成树大小一样，那么求出的就是不严格的次小生成树（因为一张图的最小生成树可以有多个，此时求出了另一个最小生成树）

求严格次小生成树（思路篇）

看到“严格次小生成树”，你的第一反应应该是“这个东西会和最小生成树有关！”

所谓“次小”就是除了最小之外的最小的，那么我们先求出最小的，起码不会对我们的求解起阻碍作用吧

假设你已经顺手使用\(Prim\)或者\(Kruskal\)算法求出了这张图的最小生成树

现在，我们可以把这个图上的所有边简单的分成两类了——第一类是在最小生成树上的边（简称树边），第二类是不在最小生成树上的边（简称非树边）

还是一开始的那个图，最小生成树上的边使用蓝笔标出，我们已知这个最小生成树的大小\(size=7\)

可以贪心的转化问题——求第二小，也就是求一个新的生成树大小\(size'\)在比\(size\)小的前提下最大

因为严格次小生成树和最小生成树一定不是同一棵树，那么我们可以考虑用一些非树边，替换掉同等数量的树边

想到替换时，也许你会遇到这些问题，（以下用三元组\((a,b,c)\)表示连通\(a、b\)两点的边，权值为\(c\)）

1. 替换时，怎么保证求出的是\(2\)小而不是\(3\)小、\(4\)小、\(n\)小呢？

根据上面的贪心思路：替换后使得\(size'-size\)最小，那么\(size'\)就是严格次小生成树

2. 一条非树边可以替换掉哪些树边？

显然不可以胡乱替换，因为需要保证求出的次小生成树还有个树的模样（不能出现环、必须连通）

想到利用树的性质：当我们要向一棵树中加入一条边时，会形成且仅形成一个环，并且这个环包含\(a\rightarrow LCA(a,b)\)和\(b\rightarrow LCA(a,b)\)路径中的所有边

我们先把一条非树边\((a,b,c)\)加进去，在\(a\rightarrow LCA(a,b)\)和\(b\rightarrow LCA(a,b)\)路径中的边中删除一条即可保证树的性质

上面的解释理解不能？请看下面的图，帮助理解：

如图，黑色的是树边，现在要把一条绿色的非树边\((8,6,n)\)加进去，那么图中标红的树边就可以被替换

书面证明

对于一棵树\(T\)其中任意两个节点\(a,b\)都存在且仅存在一条简单路径：\(a\rightarrow LCA(a,b)\rightarrow b\)
现在连接\((a,b)\)，那么上式可以写成这样：\(a\rightarrow LCA(a,b)\rightarrow b\rightarrow a\)，显然构成一个环
PS：另外，因为连接\((a,b)\)之前路径只有一条，所以连接后，形成的环也只有一个

证毕

3. 用几条非树边替换几条树边呢？

在解决这个问题之前，先给出另一个结论：

对于任意一条非树边\((a,b,c)\)，在把它加入最小生成树后形成的环中，每一条树边的权值\(w\leq c\)

解决这个问题，需要用到这个结论，所以我们先来证明一下它

证明

设加入的非树边是\((a,b,c)\),产生环包含树边的集合是\(T\)，\(w_e\)表示\(e\)的边权，最小生成树的大小为\(size\)
反证法：
设\(p:\exists e\in T\)且有\(w_e>c\)
假设\(p\)为真，那么此时断掉树边\(e\)，加入非树边\((a,b,c)\)会使得\(size\)减小
但是\(size\)是我们所求出的最小生成树的大小，它不可能更小了，所以\(p\)为假
那么\(!p:\forall e\in T w_e\leq c\)一定为真

证毕

有了上面的结论还不够，要想继续解决这个问题，我们还得大胆猜想，小心求证

做出假设：替换\(1\)条边最优

证明

还记得我们的贪心思路吗：替换后使得\(size'-size\)最小，那么\(size'\)就是严格次小生成树
我们假设用一条非树边\(e_1\)去替换一条树边，运用上面的结论，我们知道所有与\(e_1\)构成环的边的权值\(w\geq w_{e_1}\)
如果我们做这次替换，\(size'\)的大小就会比\(size\)大\(k=w-w_{e_1}\)
考虑特殊情况，\(k=0\)时，代表着我们把两条权值相等的树边和非树边做了替换
但是这么做对\(size'\)没有任何影响，只对次小生成树的形态有影响，但它长得好不好看我们并不关心，我们只关心\(size'\)而已
因为\(k=0\)时，对\(size'\)没有影响，排除这种情况，现在\(k\)的范围\((k>0)\)
（注意我们以后都不再考虑\(k=0\)的情况了！！！）
显然我们选择\(n\)条边，就会产生多个\(k\)值，此时\(size'\)一定大于只选\(1\)条边的\(size'\)
根据贪心思路，要求\(size'\)最小，显然选\(1\)条边做替换最优

证毕

问题解决，选择\(1\)条边做替换最优（也就是最小生成树和次小生成树中权值不相同的边有且只有\(1\)条）

4. 用哪条非树边替换哪条树边？答案怎么更新？
这两个我们逃不掉得枚举其中一个了，这里显然枚举非树边比较方便(设树边边权为\(w\))

因为我们要求\(size'\)最大的，所以要求\((c-w>0)\)且\((c-w)\)尽量小，因为\(c\)一定，只要使得\(w\)尽量大即可（注意这里根据上面的结论，\(c\geq w\)所以不用担心\(c-w<0\)的情况）

枚举每一个非树边\((a,b,c)\)，找到路径\(a\rightarrow LCA(a,b)\)和\(b\rightarrow LCA(a,b)\)中\(w\)最大的那条边，做替换即可，答案就是\(size'=min(size',size+c-w)\)

注意一下小细节：因为\(w\)有可能等于\(c\)，如果做替换的话，求出的并不是严格次小生成树，所以还需要记录一个次大值\(w'\)，如果\(w=c\)，那么答案\(size'=min(size',size+c-w')\)

啰啰嗦嗦这么多，按照上面的思路，就可以求严格次小生成树了

求严格次小生成树（实现篇）

明确了思路，有没有感到干劲十足呢？（必须得干劲十足啊，笔者可是\(1\)小时写完，\(7\)小时\(debug\)的男人）

这里梳理一下我们要用的算法和数据结构吧：

1. 求最小生成树：并查集，\(Kruskal\)，无脑存边

2. 最近公共祖先\(LCA\)：树上倍增，\(dfs\)预处理，邻接表

3. 区间最大/次大\(RMQ\)：树上\(st\)表

4. 一句提醒：不开\(long\) \(long\)见祖宗

所以得到公式：基础算法+数据结构+简单证明=毒瘤题（这题其实出的挺好的，既没超纲，又有一定难度）

大体框架有了，剩下的都是代码实现的细节了，就都在代码注释里讲解吧

求严格次小生成树（代码篇）

#include
#include
#include
#include
#include
#include
#include