题解

先构建出最小生成树，如果删的是非树边，直接输出答案

否则问题转化为，把该边删掉后剩下两个联通块，两个端点分别在两个块内的最小边权，LCT可以维护

不妨换一种思考方向：考虑一条非树边可以代替哪些树边，根据次小生成树的套路，它可以代替树上两端点之间路径上的任意一条边

因此，对MST进行树链剖分，然后对每一条非树边更新它两端点之间路径的最小值即可

注意：题目给的图可能不连通，需要特判！

#include
    
     #define REP(i,a,b) for(int i(a);i<=(b);++i)#define dbg(...) fprintf(stderr,__VA_ARGS__)using namespace std;typedef long long ll;typedef unsigned int uint;typedef unsigned long long ull;typedef pair
     
      pii;inline int read(){char c,p=0;int w;    while(isspace(c=getchar()));if(c=='-')p=1,c=getchar();    for(w=c&15;isdigit(c=getchar());w=w*10+(c&15));return p?-w:w;}template
      
       inline char smin(T&x,const U&y){return x>y?x=y,1:0;}template
       
        inline char smax(T&x,const U&y){return x
        
                     inline void read(T&w){register char c,p=0;                while(isspace(c=gc()));if(c=='-')p=1,c=gc();w=c^48u;                while(isdigit(c=gc()))w=w*10+(c^48u);if(p)w=-w;            }        inline int read(){register int x;return read(x),x;}        inline void flush(){fwrite(wbuf,1,oS-wbuf+1,stdout);oS=wbuf-1;}        ~FastIO(){flush();}        inline FastIO&operator<<(const char&c){if(oS>oT)flush();*++oS=c;}        inline void putstr(const string&s){            const int l=s.length();            if(oS>oT)flush();            for(int i=0;i
         
           inline FastIO&operator<<(T x){ static char stk[30];int top=0; if(oS>oT)flush(); if(x==0)return *++oS='0',*this; if(x<0)x=-x,*++oS='-'; for(;x;x/=10)stk[++top]=x%10^48; while(top)*++oS=stk[top--]; return*this; } };}IOManager::FastIO io;#define read io.readconst int N=50005;int n,m,tot,head[N],vis[N<<1],to[N<<1],nxt[N<<1],top[N],siz[N],in[N],son[N],dep[N],fa[N],cnt;struct edge{int u,v,w,id;}a[N<<1],b[N<<1];inline void add(int x,int y){to[++tot]=y,nxt[tot]=head[x];head[x]=tot;}#define y to[i]inline void go1(int x){ siz[x]=1; for(int i=head[x];i;i=nxt[i])if(y!=fa[x]) fa[y]=x,dep[y]=dep[x]+1,go1(y),siz[x]+=siz[y],siz[y]>siz[son[x]]&&(son[x]=y);}inline void go2(int x,int anc){ in[x]=++cnt,top[x]=anc; if(!son[x])return;go2(son[x],anc); for(int i=head[x];i;i=nxt[i])if(y!=fa[x]&&y!=son[x])go2(y,y);}#undef yinline bool cmp(edge x,edge y){return x.w
          
           tag[o])return; if(x<=l&&r<=y)return (void)(tag[o]=z); int mid=l+r>>1; if(x<=mid)update(ls,l,mid,x,y,z); if(y>mid)update(rs,mid+1,r,x,y,z);}inline int ask(int o,int l,int r,int x){ int ans=tag[0]; while(1){ smin(ans,tag[o]); if(l==r)return ans; int mid=l+r>>1; x<=mid?(o=ls,r=mid):(o=rs,l=mid+1); } return -1;}inline void update(int x,int y,int z){ while(top[x]^top[y]){ if(dep[top[x]]
           
            dep[y])swap(x,y); update(1,1,n,in[x]+1,in[y],z);}int main(){ n=read(),m=read(); REP(i,1,m)a[i]=b[i]=(edge){read(),read(),read(),i}; sort(a+1,a+1+m,cmp); int ans=0; REP(i,1,m){ int x=find(a[i].u),y=find(a[i].v); if(x!=y) add(a[i].u,a[i].v),add(a[i].v,a[i].u), pa[x]=y,vis[a[i].id]=1,ans+=a[i].w; } go1(1),go2(1,1); if(siz[1]
           
          
         
        
       
      
     
    

UPD.20181107

根据的思想，这题可以用并查集优化，思路与上文相同

复杂度 \(O(\alpha(n)\times n)\)

代码没时间写了，就咕了吧。。