题目描述：https://www.luogu.org/problemnew/show/P4180
解析：首先考虑如何求不严格次小生成树，即所求生成树的边权总和大于等于最小生成树的边权总和。发现不严格次小生成树一定由最小生成树上的边替换掉某条边而得，于是想到枚举非树边。发现一条非树边(u,v)只能替换掉最小生成树上路径(u,v)中的最大值。于是问题边转换成了如何求树上路径的最大值，用树剖即可。(笔者水平太菜，不会写倍增)。
其次考虑怎么求严格次小生成树。考虑怎么维护一段区间的次大值，发现如果这段区间左区间的最大值大于右区间的最大值，那么这段区间的次大值就是左区间的次大值和右区间的最大值取max，反之亦然。如果这段区间左区间的最大值等于右区间的最大值，那么这段区间的次大值就是左区间的次大值和右区间的次大值取max。于是想到用pair来存最大值与次大值。
细节：1.这道题需要边转点，在最后树剖完当top[u]==top[v]时，区间查询不是查[finc[u],finc[v]]，而是[finc[u]+1,finc[v]](finc为dfs序)。因为如果查的是[finc[u],finc[v]]的话，会将u点上面的路径一起计算，而这时不行的。2.记得最大值开1e14.
附上代码：
#include<cstdio> #include<algorithm> using namespace std; typedef long long LL; typedef pair<LL,LL> pii; const int MAXN=1000005,MAXM=3000005; int n,m; struct Edge{ int u,v; LL val; void init(){ scanf("%d%d%lld",&u,&v,&val); } }edge[MAXM]; int fa1[MAXN]; int vis[MAXM]; int head[MAXN]; struct Edg{ int to,last,val; }edg[2*MAXN]; int cnt=0; int fa[MAXN],size[MAXN],son[MAXN],dep[MAXN]; int inc[MAXN],finc[MAXN],top[MAXN]; int timer=0; LL v[MAXN]; int root=1; int lson[2*MAXN],rson[2*MAXN]; LL Max[2*MAXN],sec_Max[2*MAXN]; int ndnum=0; LL ans1=0,ans=1e14; bool cmp(Edge a,Edge b){ return a.val<b.val; } int find(int x){ if(x==fa1[x]) return x; else return fa1[x]=find(fa1[x]); } void Init(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) edge[i].init(); for(int i=1;i<=n;i++) fa1[i]=i; sort(edge+1,edge+m+1,cmp); for(int i=1;;i++){ int u=edge[i].u,v=edge[i].v; int fa_u=find(u),fa_v=find(v); if(fa_u==fa_v) continue; vis[i]=1; ans1+=edge[i].val; cnt++; fa1[fa_u]=fa_v; if(cnt==n-1) break; } } void addedge(int u,int v,int val){ edg[++cnt].to=v; edg[cnt].last=head[u]; edg[cnt].val=val; head[u]=cnt; } void dfs1(int x,int f){ size[x]=1;fa[x]=f;dep[x]=dep[f]+1; for(int i=head[x];i;i=edg[i].last){ int y=edg[i].to; if(y==f) continue; v[y]=edg[i].val; dfs1(y,x); size[x]+=size[y]; if(size[y]>size[son[x]]||son[x]==0) son[x]=y; } } void dfs2(int x,int tp){ top[x]=tp;inc[++timer]=x;finc[x]=timer; if(son[x]) dfs2(son[x],tp); for(int i=head[x];i;i=edg[i].last){ int y=edg[i].to; if(y==fa[x]||y==son[x]) continue; dfs2(y,y); } } LL max(LL x,LL y){ return x>y?x:y; } void update(int t){ if(Max[lson[t]]>Max[rson[t]]){ Max[t]=Max[lson[t]]; sec_Max[t]=max(Max[rson[t]],sec_Max[lson[t]]); } else if(Max[lson[t]]<Max[rson[t]]){ Max[t]=Max[rson[t]]; sec_Max[t]=max(Max[lson[t]],sec_Max[rson[t]]); } else{ Max[t]=Max[lson[t]]; sec_Max[t]=max(sec_Max[lson[t]],sec_Max[rson[t]]); } } void buildtree(int &t,int l,int r){ t=++ndnum; if(l==r){ Max[t]=v[inc[l]]; sec_Max[t]=0; return; } int mid=(l+r)>>1; buildtree(lson[t],l,mid);buildtree(rson[t],mid+1,r); update(t); } void Prework(){ for(int i=1;i<=m;i++){ if(vis[i]){ int u=edge[i].u,v=edge[i].v,val=edge[i].val; addedge(u,v,val); addedge(v,u,val); } } dfs1(root,0); dfs2(root,root); buildtree(root,1,n); } LL min(LL a,LL b){ return a<b?a:b; } pii get_max(pii a,pii b){ LL res1,res2; if(a.first>b.first){ res1=a.first; res2=max(a.second,b.first); } else if(a.first<b.first){ res1=b.first; res2=max(b.second,a.first); } else{ res1=a.first; res2=max(a.second,b.second); } return make_pair(res1,res2); } pii query(int t,int l,int r,int L,int R){ if(L<=l&&r<=R) return make_pair(Max[t],sec_Max[t]); int mid=(l+r)>>1; pii res; if(L<=mid) res=get_max(res,query(lson[t],l,mid,L,R)); if(R>mid) res=get_max(res,query(rson[t],mid+1,r,L,R)); return res; } pii Query(int u,int v){ pii res; while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]]) swap(u,v); res=get_max(res,query(root,1,n,finc[top[u]],finc[u])); u=fa[top[u]]; } if(dep[u]>dep[v]) swap(u,v); if(dep[u]!=dep[v]) res=get_max(res,query(root,1,n,finc[u]+1,finc[v])); return res; } void opt(int x){ int u=edge[x].u,v=edge[x].v; pii res=Query(u,v); if(edge[x].val>res.first){ LL anss=ans1; ans=min(ans,anss-res.first+edge[x].val); } else if(res.second){ LL anss=ans1; ans=min(ans,anss-res.second+edge[x].val); } } void work(){ for(int i=1;i<=m;i++) if(!vis[i]) opt(i); printf("%lld",ans); } int main(){ Init(); Prework(); work(); return 0; }