Link Cut Tree 求最小生成树

对边建点，原图中的边转化为 点的点 - 边的点 - 点的点

于是用 LCT 维护连通关系，并支持查询最大值位置即可

#include <bits/stdc++.h>
using namespace std;

const int N = 300005;

int n,m,val[N],t1,t2,t3;

namespace lct {
    int top, q[N], ch[N][2], fa[N], rev[N];
    int mx[N];
    inline void pushup(int x){
        int v=max(val[x], max(val[mx[ch[x][0]]],val[mx[ch[x][1]]]));
        mx[x]=x;
        if(v==val[mx[ch[x][0]]]) mx[x]=mx[ch[x][0]];
        if(v==val[mx[ch[x][1]]]) mx[x]=mx[ch[x][1]];
    }
    inline void pushdown(int x){
        if(!rev[x]) return;
        rev[ch[x][0]]^=1;
        rev[ch[x][1]]^=1;
        rev[x]^=1;
        swap(ch[x][0],ch[x][1]);
    }
    inline bool isroot(int x){
        return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x;
    }
    inline void rotate(int p){
        int q=fa[p], y=fa[q], x=ch[fa[p]][1]==p;
        ch[q][x]=ch[p][x^1]; fa[ch[q][x]]=q;
        ch[p][x^1]=q; fa[q]=p; fa[p]=y;
        if(y) if(ch[y][0]==q) ch[y][0]=p;
        else  if(ch[y][1]==q) ch[y][1]=p;
        pushup(q); pushup(p);
    }
    inline void splay(int x){
        q[top=1]=x;
        for(int i=x;!isroot(i);i=fa[i]) q[++top]=fa[i];
        for(int i=top;i;i--) pushdown(q[i]);
        for(;!isroot(x);rotate(x))
            if(!isroot(fa[x]))
                rotate((ch[fa[x]][0]==x)==(ch[fa[fa[x]]][0]==fa[x])?fa[x]:x);
    }
    void access(int x){
        for(int t=0;x;t=x,x=fa[x])
            splay(x),ch[x][1]=t,pushup(x);
    }
    void makeroot(int x){
        access(x);
        splay(x);
        rev[x]^=1;
    }
    int find(int x){
        access(x);
        splay(x);
        while(ch[x][0]) x=ch[x][0];
        return x;
    }
    void split(int x,int y){
        makeroot(x);
        access(y);
        splay(y);
    }
    void cut(int x,int y){
        split(x,y);
        if(ch[y][0]==x)
            ch[y][0]=0, fa[x]=0;
    }
    void link(int x,int y){
        makeroot(x);
        fa[x]=y;
    }
    int query(int x,int y) {
        split(x,y);
        return mx[y];
    }
}

int ei[N],ej[N];

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int ans=0;
    for(int i=1;i<=m;i++) {
        cin>>t1>>t2>>t3;
        val[i+n]=t3;
        ei[i]=t1;
        ej[i]=t2;
        if(lct::find(t1)!=lct::find(t2)) {
            lct::link(t1,n+i);
            lct::link(t2,n+i);
            ans+=t3;
        }
        else {
            int mp=lct::query(t1,t2);
            if(val[mp]>t3) {
                lct::cut(mp,ei[mp-n]);
                lct::cut(mp,ej[mp-n]);
                ans-=val[mp];
                lct::link(t1,n+i);
                lct::link(t2,n+i);
                ans+=t3;
            }
        }
    }
    cout<<ans<<endl;
}