描述：
就是求一个次小生成树的边权和
题解
我们先构造一个最小生成树， 把树上的边记录下来。
然后再枚举每条非树边(u, v, val)，在树上找出u 到v 路径上的最小边$g_0$ 和 严格次小边 $g_1$
如果$val > g_0$就可以考虑把$g_0$ 替换成$val$ 并记录答案。
如果$val = g_0$ 就把$g_1$替换成$val$ 记录答案。
然后我们就需要快速求出树链上的最小和次小边， 需要用树上倍增求LCA类似的方法求。
定义$g[0][ i ][ j ]$ 表示从$j$ 到第 $2^i$ 辈祖先中的最小边， $g[1][ i ][ j ] $表示从$j$ 到 第$2^i$ 辈祖先中的次小边， 满足以下关系：
1: $g[0][ i ][ j ] = \max( g[0][ i - 1][ j ], g[0][ i - 1][ f[i - 1][ j ]]) $
2 :$ g[1][ i ][ j ] = \max( g[1][ i - 1][ j ], g[1][ i - 1 ][ f[i - 1][ j ]]) $ 当$g[0][i - 1][ j ] = g[0][ i - 1][ f[i - 1][ j ]] $
3: $ g[1][ i ][ j ] = \max(g[0][ i - 1][ j ], g[1][ i - 1][ f[i - 1][ j ]])$ 当$g[0][i - 1][ j ] < g[0][ i - 1][ f[i - 1][ j ]] $
4: $ g[1][ i ][ j ] = \max(g[1][ i - 1][ j ], g[0][ i - 1][ f[i - 1][ j ]])$ 当$g[0][i - 1][ j ] > g[0][ i - 1][ f[i - 1][ j ]] $
倍增求树链上的最小和次小值时同理合并
题解
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rd read()
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define per(i,a,b) for(register int i = (a); i >= (b); --i)
#define ll long long
using namespace std; const int N = 5e5;
const int inf = ~0U >> ; int n, m;
ll sum, ans = 1e18;
int fa[N], f[][N], g[][][N], dep[N];
int head[N], tot; struct edge {
int nxt, to, val;
}e[N << ]; struct node {
int u, v, val, mk;
}E[N << ]; inline int read() {
int X = , p = ; char c = getchar();
for(; c > '' || c < ''; c = getchar()) if(c == '-') p = -;
for(; c >= '' && c <= ''; c = getchar()) X = X * + c - '';
return X * p;
} inline void added(int u, int v, int val) {
e[++tot].to = v;
e[tot].nxt = head[u];
e[tot].val = val;
head[u] = tot;
} inline void add(int u, int v, int val) {
added(u, v, val); added(v, u, val);
} inline int fd(int x) {
return fa[x] == x ? x : fa[x] = fd(fa[x]);
} inline int cmp(const node &A, const node &B) {
return A.val < B.val;
} inline void dfs(int u) {
for(int i = head[u]; i; i = e[i].nxt) {
int nt = e[i].to;
if(nt == f[][u]) continue;
f[][nt] = u;
g[][][nt] = e[i].val;
g[][][nt] = -inf;
dep[nt] = dep[u] + ;
dfs(nt);
}
} inline void LCA(int x, int y, int &a, int &b) {
int g0, g1;
if(dep[x] < dep[y]) swap(x, y);
for(int i = ; ~i; --i) if(dep[f[i][x]] >= dep[y]) {
g0 = g[][i][x]; g1 = g[][i][x];
if(g0 == a) b = max(b, g1);
if(g0 > a) b = max(a, g1);
if(g0 < a) b = max(g0, b);
a = max(a, g0);
x = f[i][x];
}
for(int i = ; ~i; --i) if(f[i][x] != f[i][y]) {
g0 = g[][i][x]; g1 = g[][i][x];
if(g0 == a) b = max(b, g1);
if(g0 > a) b = max(a, g1);
if(g0 < a) b = max(g0, b);
a = max(a, g0); g0 = g[][i][y]; g1 = g[][i][y];
if(g0 == a) b = max(b, g1);
if(g0 > a) b = max(a, g1);
if(g0 < a) b = max(g0, b);
a = max(a, g0);
x = f[i][x]; y = f[i][y];
} g0 = g[][][x]; g1 = g[][][x];
if(g0 == a) b = max(b, g1);
if(g0 > a) b = max(a, g1);
if(g0 < a) b = max(g0, b);
a = max(a, g0); g0 = g[][][y]; g1 = g[][][y];
if(g0 == a) b = max(b, g1);
if(g0 > a) b = max(a, g1);
if(g0 < a) b = max(g0, b);
a = max(a, g0);
} int main()
{
n = rd; m = rd;
rep(i, , n) fa[i] = i;
rep(i, , m) {
int u = rd, v = rd, val = rd;
E[i].u = u; E[i].v = v; E[i].val = val; E[i].mk = ;
}
sort(E+, E++m, cmp);
rep(i, , m) {
int x = fd(E[i].u), y = fd(E[i].v);
if(x == y) continue;
sum += E[i].val;
fa[y] = x;
E[i].mk = ;
add(E[i].u, E[i].v, E[i].val);
}
dep[] = ;
dfs();
rep(i, , ) rep(j, , n) {
f[i][j] = f[i - ][f[i - ][j]];
g[][i][j] = max(g[][i - ][j], g[][i - ][f[i - ][j]]);
int tmp = -inf;
if(g[][i - ][j] == g[][i - ][f[i - ][j]]) tmp = max(g[][i - ][j], g[][i - ][f[i - ][j]]);
if(g[][i - ][j] < g[][i - ][f[i - ][j]]) tmp = max(g[][i - ][j], g[][i - ][f[i - ][j]]);
if(g[][i - ][j] > g[][i - ][f[i - ][j]]) tmp = max(g[][i - ][j], g[][i - ][f[i - ][j]]);
g[][i][j] = tmp;
}
rep(i, , m) if(!E[i].mk) {
int x = E[i].u, y = E[i].v, g0 = -inf, g1 = -inf;
LCA(x, y, g0, g1);
if(E[i].val == g0 && g1 != -inf) ans = min(ans, sum + E[i].val - g1);
if(E[i].val > g0) ans = min(ans, sum + E[i].val - g0);
}
printf("%lld\n",ans);
}