次小生成树问题的高效求解

在解决严格次小生成树问题时，初始阶段容易遇到一些特殊情况，例如所有边权重相等的情况，这可能导致程序输出错误结果。为了解决这个问题，我们可以采用以下步骤：

1. **构建最小生成树**：使用Kruskal算法或Prim算法构建最小生成树。
2. **枚举非树边**：对于每一条不在最小生成树中的边，尝试将其加入树中形成一个环。
3. **更新最大和次大边**：当新边加入后，找到该环上的最大边和次大边。如果新边可以替换最大边或次大边，则更新答案。
4. **倍增法维护路径信息**：利用倍增法（Binary Lifting）维护链上的最大边和次大边，并结合最近公共祖先（LCA）算法快速查询路径上的关键信息。

以下是实现上述逻辑的具体代码示例：

```cpp
#include
#include
#include
#include
#include
#include
typedef long long LL;
using namespace std;
const int maxn = 100000 + 299;
const int maxm = 300000 * 2 + 299;
int upp = 0, tot, n, m, k, ecnt, fir[maxn], nxt[maxm], to[maxm], vis[maxn], fa[maxn];
int f[maxn][32], R[maxn];
LL st[maxn][32], stc[maxn][32], ans, rem, rec, val[maxm], anspre;
struct edge {
int u, v, w, is;
friend bool operator<(const edge &A, const edge &B) {
return A.w }
} e[maxm];

void add(int u, int v, int w) {
nxt[++ecnt] = fir[u]; fir[u] = ecnt; to[ecnt] = v; val[ecnt] = (LL)w;
nxt[++ecnt] = fir[v]; fir[v] = ecnt; to[ecnt] = u; val[ecnt] = (LL)w;
}

void init() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
}

int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

void kruskal() {
sort(e + 1, e + m + 1);
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i <= m; i++) {
int u = e[i].u, v = e[i].v;
int fu = find(u), fv = find(v);
if (fu != fv) {
e[i].is = 1;
anspre += e[i].w;
add(u, v, e[i].w);
tot++;
if (tot == n - 1) break;
fa[fu] = fv;
}
}
}

void dfs(int x, int ff) {
f[x][0] = ff; R[x] = R[ff] + 1;
for (int i = fir[x]; i; i = nxt[i]) if (to[i] != ff) {
st[to[i]][0] = val[i];
stc[to[i]][0] = val[i];
dfs(to[i], x);
}
}

void make_st() {
for (int i = 1; i <= 30; i++)
for (int j = 1; j <= n; j++) {
f[j][i] = f[f[j][i - 1]][i - 1];
int u = st[j][i - 1], v = st[f[j][i - 1]][i - 1];
st[j][i] = max(u, v);
if (u && v && u != v) stc[j][i] = min(u, v);
if (stc[j][i - 1]) stc[j][i] = max(stc[j][i], stc[j][i - 1]);
if (stc[f[j][i - 1]][i - 1]) stc[j][i] = max(stc[j][i], stc[f[j][i - 1]][i - 1]);
}
}

int swapp(LL x, LL &zd, LL &cd) {
if (x == zd) return 0;
if (x > zd) {
cd = max(cd, zd);
zd = x;
} else cd = max(cd, x);
}

int lca(int x, int y) {
rem = 0, rec = 0;
if (R[x] for (int i = 30; i >= 0; i--) {
if (R[f[x][i]] >= R[y]) {
if (rem && st[x][i] > rem) rec = max(rem, rec);
rem = max(rem, st[x][i]);
if (i != 0) rec = max(rec, stc[x][i]);
x = f[x][i];
}
}
if (x == y) return 1;
for (int i = 30; i >= 0; i--) {
if (f[x][i] != f[y][i]) {
swapp(stc[y][i], rem, rec);
swapp(stc[x][i], rem, rec);
swapp(st[x][i], rem, rec);
swapp(st[y][i], rem, rec);
x = f[x][i]; y = f[y][i];
}
}
swapp(stc[y][0], rem, rec);
swapp(stc[x][0], rem, rec);
swapp(st[x][0], rem, rec);
swapp(st[y][0], rem, rec);
return 1;
}

void work() {
ans = 1e18;
for (int i = 1; i <= m; i++) if (e[i].is != 1) {
int x = e[i].u, y = e[i].v;
lca(x, y);
if (e[i].w != rem) ans = min(ans, anspre - rem + e[i].w);
else if (e[i].w != rec) ans = min(ans, anspre - rec + e[i].w);
}
printf("%lld\n", ans);
}

int main() {
init();
kruskal();
dfs(1, 0);
make_st();
work();
return 0;
}
```