前言

记录一下，顺便捋一捋思路。

前置知识

• 最小生成树 \(\tt{Kruskal}\)
• 树上倍增
• \(\tt{LCA}\)

非严格次小生成树

有一种贪心的做法，我们先得出该无向图的最小生成树，最小生成树上的边称为树边，反之为非树边。先可以得到一个定理，次小生成树与最小生成树一定只有一条边不同，也就是次小生成树中含有一条非树边代替了一条树边。

可以用反证法证明，若存在多于一条边不同，那么此时的生成树没有只存在一条边不同的生成树更优，原因显然。

因此我们可以先求出最小生成树，再考虑用非树边替换树边。

而现在的问题在于如何保证替换后所得到的是一个树形结构。可以发现，我们要替换的这条非树边的两个节点一定与最小生成树中这两个节点的路径构成环。那么我们可以删除该环中任意一条边，所得到的一定是树形结构。考虑删去掉哪条边，很明显删去边权最大的一条边。这样才可以最小化该边与非树边的差值。

那么我们就只要枚举每条非树边，并用非树边的两个节点在生成树中构成的路径的最大边来替换即可。而路径的求法就是先求出两个节点的最近公共祖先，然后再向上跳。

\(\tt{Kruskal}\) 求最小生成树是 \(\Theta(m \log m)\)，最大值可以用树上倍增来维护，与 \(\tt{LCA}\) 一样，均用倍增维护，时间复杂度 \(\Theta(n \log n)\)，所以总时间复杂度是 \(\Theta(m \log m+n \log n)\).

严格次小生成树

注意到严格，也就是说不能存在等于的情况。那么以非严格次小生成树的求法为基础，我们只需要再维护一个次大值即可。

当我们要替换的树边与非树边权值相等时，我们就用次大的树边来替换。

时间复杂度同上。

题目

P4180

评价

用处不大，不该看做一个板子，调试很费劲，代码调的比较乱，就不放了。