严格次小生成树
题解小蓝书 + 我自己的补充
做法题意很好理解吧。
设最小生成树的边权之和为 \(sum\)。
我们要找严格次小生成树，就是要找到这样的一条非最小生成树上的边，满足：
将最小生成树上的某条边替换成这条边后，树依然联通。
这条边与被替换边的权值之差最小，且大于 \(0\)。
所以我们进行如下操作：
选择一条非最小生成树上的边 \((x,y,z)\)。
将它加入树中，显然会形成一个环。
由 \(Kruskal\) 的证明过程我们可以得到，\(z \geq dis_{x,y}\)。
所以我们可以将 \(x\) - \(y\) 路径上的某条边替换成边 \((x,y,z)\) ，显然树依然联通。
设\(x\) - \(y\) 路径上的权值最大边的边权为 \(val_1\) ，次大边的边权为 \(val_2\) 。
根据上述严格次小生成树的找法的定义， 当 \(z > val_1\) 时 ，将 \(val_1\) 的这条边替换成 \((x,y,z)\) 肯定是最优的，得到候选答案 \(sum - val_1 + z\)。当 \(z = val_1\) 时，将 \(val_2\) 替换成 \((x,y,z)\) 肯定是最优的，因为 \(val_1\) 所在的边不能被替换，得到候选答案 \(sum - val_2 + z\)。
对所有的非树边执行上述操作，记录最小的范围值，得到最终答案。
优化显然每次暴查 \(val_1,val_2\) 明显会炸。
所以我们可以运用倍增的思想预处理出点 \(x\) 向上跳 \(2^k\) 次的路径中的 \(val_1\) 和 \(val_2\)。
做法类似与 \(lca\) 倍增做法时维护祖先的做法，这到题我们在找 \(x\) - \(y\) 的路径时也需要 \(lca\) ，所以这两个我们也需要维护出来。
设 \(g[x][k][0/1]\) 表示点 \(x\)，向上跳 \(2^k\) 次的路径中的 \(val_1\) 和 \(val_2\)。
初始化：
\[g[x][0][0] = w_{x,fa_x},g[x][0][1] = -INF(设为负无穷不为影响到其它值的维护) \]