原题链接：P4081
题意
给定一颗 \(n\) 个点 \(m\) 条边的树，求这棵树的严格次小生成树。
严格次小生成树指：边权和大于最小生成树，且边权和最小的生成树。
思路
首先可以用克鲁斯卡尔求出这棵树的最小生成树，然后考虑用类似于反悔贪心的思路来做。
对于每一条不在最小生成树中的边 \(u \to v\)，我们可以把这条边加入生成树中，然后再把一条原本在 \(u\) 到 \(v\) 的路径上且在最小生成树中的边删掉。那么这条边必须要满足的条件是边权小于 \(u \to v\) 的边权且尽可能大。所以很容易想到先树剖，然后再用一个 ST 表维护区间的最大值和严格次大值。跳重链的时候也动态维护最大值和次大值即可。注意最大值不能等于次大值，因为要求严格小于，否则 90 pts。
另：CF609E 是这道题的弱化版，只需要维护最大值即可。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f
#define inf_db 127
#define ls id << 1
#define rs id << 1 | 1
#define re register
#define endl '\n'
typedef pair <int,int> pii;
const int MAXN = 3e5 + 10;
int n,m,head[MAXN],cnt,f[MAXN],depth[MAXN],size[MAXN],fa[MAXN],st[MAXN * 3][21],Ans = 1e18;
int idx[MAXN],timestamp,son[MAXN],top[MAXN],ans,val[MAXN],a[MAXN],sec[MAXN * 3][21];
bool vis[MAXN];
struct Node{int u,v,w,nxt;}e[MAXN << 1];
struct Edge{int x,y,z,id;}g[MAXN];
struct edge{int x,y,z;}p[MAXN];
inline void Add(int u,int v,int w){e[++cnt] = {u,v,w,head[u]};head[u] = cnt;}
inline bool cmp(Edge x,Edge y){return x.z < y.z;}
inline int Find(int x)
{
if(x == f[x]) return f[x];
else return f[x] = Find(f[x]);
}
inline void dfs(int u,int father)
{
depth[u] = depth[father] + 1,fa[u] = father,size[u] = 1;
for(int i = head[u]; ~ i;i = e[i].nxt)
{
int now = e[i].v;
if(now == father) continue;
dfs(now,u);
size[u] += size[now],a[now] = e[i].w;
if(size[now] > size[son[u]]) son[u] = now;
}
}
inline void sdfs(int u,int father,int t)
{
idx[u] = ++timestamp,top[u] = t,val[idx[u]] = a[u];
if(son[u] == 0) return;
sdfs(son[u],u,t);
for(int i = head[u]; ~ i;i = e[i].nxt)
{
int now = e[i].v;
if(now == father || now == son[u]) continue;
sdfs(now,u,now);
}
}
inline int Query(int u,int v,int w)
{
int res1 = -6e18,res2 = -6e18;
while(top[u] != top[v])
{
if(depth[top[u]] < depth[top[v]]) swap(u,v);
int l = idx[top[u]],r = idx[u];
int lg = log2(r - l + 1);
int tmp1 = -6e18,tmp2 = -6e18;
tmp1 = max(tmp1,max(st[l][lg],st[r - (1 << lg) + 1][lg]));
tmp2 = max(tmp2,max(sec[l][lg],sec[r - (1 << lg) + 1][lg]));
if(tmp1 > res1) res2 = max(res1 == res2 ? 0ll : res1,tmp2),res1 = tmp1;
else if(tmp1 > res2 && tmp1 != res1) res2 = tmp1;
u = fa[top[u]];
}
if(depth[u] < depth[v]) swap(u,v);
int l = idx[v] + 1,r = idx[u];
if(l > r) return (res1 < w ? res1 : res2);
int lg = log2(r - l + 1);
int tmp1 = -6e18,tmp2 = -6e18;
tmp1 = max(tmp1,max(st[l][lg],st[r - (1 << lg) + 1][lg]));
tmp2 = max(tmp2,max(sec[l][lg],sec[r - (1 << lg) + 1][lg]));
if(tmp1 > res1) res2 = max(res1 == res2 ? 0ll : res1,tmp2),res1 = tmp1;
else if(tmp1 > res2 && tmp1 != res1) res2 = tmp1;
return (res1 < w ? res1 : res2);
}
signed main()
{
memset(head,-1,sizeof head);
cin >> n >> m;
for(int i = 1;i <= n;i++) f[i] = i;
for(int i = 1;i <= m;i++) cin >> g[i].x >> g[i].y >> g[i].z,g[i].id = i;
for(int i = 1;i <= m;i++) p[i] = {g[i].x,g[i].y,g[i].z};
sort(g + 1,g + m + 1,cmp);
for(int i = 1;i <= m;i++)
if(Find(g[i].x) != Find(g[i].y))
{
f[Find(g[i].x)] = Find(g[i].y);
Add(g[i].x,g[i].y,g[i].z),Add(g[i].y,g[i].x,g[i].z);
ans += g[i].z;
vis[g[i].id] = true;
}
dfs(1,0);sdfs(1,0,1);
for(int i = 1;i <= n;i++) st[i][0] = val[i];
for(int j = 1;j <= 19;j++)
for(int i = 1;i <= n;i++)
{
st[i][j] = max(st[i][j],max(st[i][j - 1],st[i + (1 << j - 1)][j - 1]));
sec[i][j] = max(sec[i][j],max(sec[i][j - 1],sec[i + (1 << j - 1)][j - 1]));
if(st[i][j - 1] < st[i + (1 << j - 1)][j - 1] && sec[i][j] < st[i][j - 1]) sec[i][j] = st[i][j - 1];
if(st[i][j - 1] > st[i + (1 << j - 1)][j - 1] && sec[i][j] < st[i + (1 << j - 1)][j - 1]) sec[i][j] = st[i + (1 << j - 1)][j - 1];
}
for(int i = 1;i <= m;i++) if(!vis[i]) Ans = min(Ans,ans + p[i].z - Query(p[i].x,p[i].y,p[i].z));
cout << Ans;
return 0;
}