P4234 最小差值生成树

link(edge[i].u,n+i),link(n+i,edge[i].v);

splay(now);
t[t[now].ch[0]].fa=t[t[now].ch[1]].fa=0;

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+7;
const int M=2e5+7;
int st[N+M],n,m,used[M],num,ans=1<<30,tot;
int read() {
    char cc = getchar(); int cn = 0, flus = 1;
    while(cc < ‘0‘ || cc > ‘9‘) {  if( cc == ‘-‘ ) flus = -flus;  cc = getchar();  }
    while(cc >= ‘0‘ && cc <= ‘9‘)  cn = cn * 10 + cc - ‘0‘, cc = getchar();
    return cn * flus;
}
struct edge{
    int u,v,val;
    bool operator < (const edge &x)const {
        return val<x.val;
    }
}edge[M];
struct tree{
    int ch[2],fa,id=0;
    bool rev;
}t[N+M];
bool nroot(int x){
    return (t[t[x].fa].ch[0]==x)||(t[t[x].fa].ch[1]==x);
}
void rev(int x){
    swap(t[x].ch[0],t[x].ch[1]);
    t[x].rev^=1;
}
void pushdown(int x){
    if(t[x].rev){
        if(t[x].ch[0])rev(t[x].ch[0]);
        if(t[x].ch[1])rev(t[x].ch[1]);
        t[x].rev=0;
    }
}
void pushup(int x){
    t[x].id=x;//这里要注意写法
    if(t[t[x].ch[0]].id>n&&(t[x].id<=n||t[x].id>t[t[x].ch[0]].id))t[x].id=t[t[x].ch[0]].id;
    if(t[t[x].ch[1]].id>n&&(t[x].id<=n||t[x].id>t[t[x].ch[1]].id))t[x].id=t[t[x].ch[1]].id;
}
void rotate(int x){
    int y=t[x].fa;
    int z=t[y].fa;
    bool k=t[y].ch[1]==x;
    if(nroot(y))t[z].ch[t[z].ch[1]==y]=x;
    t[x].fa=z;
    t[y].ch[k]=t[x].ch[k^1];
    t[t[x].ch[k^1]].fa=y;
    t[x].ch[k^1]=y;
    t[y].fa=x;
    pushup(y);
    pushup(x);
}
void splay(int x){
    int y=0,z=x;
    st[++y]=z;
    while(nroot(z)){
        st[++y]=z=t[z].fa;
    }
    while(y)pushdown(st[y--]);
    while(nroot(x)){
        y=t[x].fa;
        z=t[y].fa;
        if(nroot(y))
            (t[y].ch[1]==x)^(t[z].ch[1]==y)?rotate(x):rotate(y);
        rotate(x);
    }
}
void access(int x){
    for(int y=0;x;y=x,x=t[x].fa){
        splay(x);
        t[x].ch[1]=y;
        pushup(x);
    }
}
void makeroot(int x){
    access(x);
    splay(x);
    rev(x);
}
int findroot(int x){
    access(x);
    splay(x);
    while(t[x].ch[0]){
        pushdown(x);
        x=t[x].ch[0];
    }
    splay(x);
    return x;
}
void split(int x,int y){
    makeroot(x);
    access(y);
    splay(y);
}
void link(int x,int y){
    makeroot(x);
    t[x].fa=y;
}
bool check(int x,int y){
    makeroot(x);
    return findroot(y)==x;
}
int main(){
    n=read();
    m=read();
    for(int i=1;i<=m;i++){
        edge[i].u=read();
        edge[i].v=read();
        edge[i].val=read();
    }
    sort(edge+1,edge+1+m);
    int j=1;
    for(int i=1;i<=m;i++){
        t[n+i].id=n+i;//初始化 
        if(edge[i].u==edge[i].v){
            used[i]=1;//可能有自己连自己的边 
            continue;
        }
        else if(!check(edge[i].u,edge[i].v)){
            link(edge[i].u,n+i),link(n+i,edge[i].v);
            ++num;//连边的次数，为n-1时即可开始更新答案 
        }
        else {
            int now;
            split(edge[i].u,edge[i].v),now=t[edge[i].v].id;
            used[now-n]=1,splay(now);
            t[t[now].ch[0]].fa=t[t[now].ch[1]].fa=0;
            link(edge[i].u,n+i),link(n+i,edge[i].v);
        }
        while(used[j]&&j<i)++j;//这里这样写相当于维护了指针，每次都再扫一次的话复杂度就炸了
        if(num>=n-1)ans=min(ans,edge[i].val-edge[j].val);
    }
    printf("%d\n",ans);
    return 0;
}