题目描述
小 (C) 最近学了很多最小生成树的算法，(Prim) 算法、(Kruskal) 算法、消圈算法等等。正当小(C)洋洋得意之时，小(P)又来泼小(C)冷水了。小(P)说，让小(C)求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是(E_M)，严格次小生成树选择的边集是(E_S)，那么需要满足：(value(e)表示边e的权值)(sum_{ein E_M}value(e)<sum_{ein E_S}value(e))
这下小 (C) 蒙了，他找到了你，希望你帮他解决这个问题。
输入输出格式
输入格式：
第一行包含两个整数(N)和(M)，表示无向图的点数与边数。接下来(M)行，每行 3个数(x y z) 表示，点(x)和点(y)之间有一条边，边的权值为(z)。
输出格式：
包含一行，仅一个数，表示严格次小生成树的边权和。
(数据保证必定存在严格次小生成树)
说明:
数据中无向图无自环;
(50\%) 的数据(N≤2000 M≤3000);
(80\%)的数据(N≤50000 M≤100000);
(100\%) 的数据(N≤100000 M≤300000);
边权值非负且不超过(10^9) 。
基本思路：
先求出最小生成树，在建树时，将所有的边划分为两个集合（树边(E_T)和非树边(E_K)）
之后考虑将(forall e(u,v)in E_K)分别加入到最小生成树上去，将树上(u,v)之间的最大边权(Maxvalue(u,v))与(value(e))作比较：
- 若(Maxvalue(u,v) e value(e)) 则得到(MST^prime)的一个候选值(MST-Maxvalue(u,v)+value(e))
- 若(Maxvalue(u,v)= value(e)) 则得到(MST^prime)的一个候选值(MST-Maxvalue^prime(u,v)+value(e))
（其中(MST^prime)为次小生成树，(Maxvalue^prime(u,v))为树上(u,v)间的次大边权）
思路确定下来之后，最严峻的问题就是：如何快速求出(Maxvalue(u,v))和(Maxvalue^prime(u,v))?
树上倍增(+LCA)
对所建立的最小生成树进行树上倍增，各元素意义如下：
- (f[ i ][ j ])表示树上编号为(i)的点向上跳(2^j)步所到达的祖先编号
- (maxg[ i ][ j ])表示树上编号为(i)的点以上长度为(2^j)的树上路径的最大边权值
- (ming[ i ][ j ])表示树上编号为(i)的点以上长度为(2^j)的树上路径的次大边权值
在求处理树上路径((u,v))时先求出(LCA(u,v))，再分为((u,LCA(u,v)))和((v,LCA(u,v)))两段处理，取两次答案的较大值作为当前的目标替换值（具体实现见代码中的(qmax)函数）
细节注意事项
个人来看，以下几点是非常重要滴：
- (Kruskal)的构树（最基本的一步，千万不能出岔子）
- 维护树上路径的边权最大值与次大值（重中之重！！！）
千万要注意(maxg)和(ming)的转移,不然就有可能像我一样一直WA第一个点(...) - (LCA)辅助查询树上路径((u,v))之间的最大边权
- 开(long long) 啊（不开(long long)见祖宗(...)）
参考代码
下面是蒟蒻的代码（欢迎大佬来踩）
//由于本地调试的时候忘了开long long，所以所有的int都是long long...qwq
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
typedef long long LL;
const LL INF=2147483647000000;//INF 开大
// 空间都开大点
const LL MAXN=400010;
const LL MAXM=900010;
using namespace std;
inline LL read(){//读优
LL s=0;bool f=false;char c=getchar();
while(c<'0'||c>'9')f|=(c=='-'),c=getchar();
while(c>='0'&&c<='9')s=(s<<3)+(s<<1)+(c^48),c=getchar();
return (f)?(-s):(s);
}
struct edge{
LL u,v,w;bool bt;//bt为false则说明为非树边，为真则为树边
void scan(){u=read(),v=read(),w=read();}
bool operator<(const edge&obj)const{return w<obj.w;}
}e[MAXM];
LL tot,head[MAXN],nxt[MAXM<<1],v[MAXM<<1],w[MAXM<<1];
inline void Add_edge(LL from,LL to,LL dis){
nxt[++tot]=head[from],head[from]=tot,v[tot]=to,w[tot]=dis;
}
LL fa[MAXN];
inline LL findd(LL k){
return fa[k]==k?k:fa[k]=findd(fa[k]);
}
LL n,m,MST=0;
inline void kruskal(){
for(LL i=1;i<=n;i++) fa[i]=i;
sort(e+1,e+1+m);
for(LL i=1;i<=m;i++){
LL u=e[i].u;
LL v=e[i].v;
LL w=e[i].w;
if(findd(u)!=findd(v)){
MST+=w;
e[i].bt=true;
Add_edge(u,v,w);
Add_edge(v,u,w);
fa[findd(u)]=findd(v);
}
}
}
LL dep[MAXN],f[MAXN][19];
LL maxg[MAXN][19],ming[MAXN][19];
inline void dfs(LL u,LL p){
for(LL i=1;i<=18;i++){
f[u][i]=f[f[u][i-1]][i-1];
maxg[u][i]=max(maxg[u][i-1],maxg[f[u][i-1]][i-1]);
//maxg肯定为两段路径分别的maxg的较大值
ming[u][i]=max(ming[u][i-1],ming[f[u][i-1]][i-1]);
//先令ming为两段路径分别的ming的较大值
//这个 if 非常重要！不然的话，要是边权最大的边有很多，就会使次大边权也为最大值
if(maxg[u][i-1]!=maxg[f[u][i-1]][i-1])
ming[u][i]=max(ming[u][i],min(maxg[u][i-1],maxg[f[u][i-1]][i-1]));
//若两段的maxg相同，则不必要继续更新ming
//否则要将ming与两段路径的maxg的较小值作比较，再次更新
}
for(LL i=head[u];i;i=nxt[i])
if(!dep[v[i]]){
f[v[i]][0]=u;
maxg[v[i]][0]=w[i];
ming[v[i]][0]=-INF;
dep[v[i]]=dep[u]+1;
dfs(v[i],u);
}
}
inline LL LCA(LL x,LL y){
if(dep[x]<dep[y]) swap(x,y);
for(LL i=18;i>=0;i--)
if(dep[f[x][i]]>=dep[y]) x=f[x][i];
if(x==y) return x;
for(LL i=18;i>=0;i--)
if(f[x][i]^f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
inline LL qmax(LL x,LL y,LL z){
LL ans=-INF;
//ans记录树上(x,y)同一条链上的最大边权
//由于主函数中求了LCA，所以在当前的函数中，y一定是x的祖先
for(LL i=18;i>=0;i--)
if(dep[f[x][i]]>=dep[y]){
//这个 if 的原理同上
//若当前这条非树边的权与当前路径段的最大边权不等
if(z!=maxg[x][i])
//则用maxg更新一次
ans=max(ans,maxg[x][i]);
else
//否则则用ming尝试更新
ans=max(ans,ming[x][i]);
x=f[x][i];
}
return ans;
}
int main(){
n=read(),m=read();
for(LL i=1;i<=m;i++) e[i].scan();
kruskal();
dep[1]=1;
maxg[1][0]=0;
ming[1][0]=-INF;
dfs(1,0);
LL _MST_=INF;
for(LL i=1;i<=m;i++){
LL u=e[i].u;
LL v=e[i].v;
LL w=e[i].w;
if(!e[i].bt){
LL lca=LCA(u,v);
LL maxx=qmax(u,lca,w);
LL maxy=qmax(v,lca,w);
_MST_=min(_MST_,MST-max(maxx,maxy)+w);
}
}
return printf("%lld",_MST_),0;
}