记录

LCT 应该没问题，求助。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f;

namespace Cms{

    const int N=400005;
    int fa[N],ch[N][2],iv[N];

    struct info{
        ll v;int id;
        info(){ v=-inf;id=-1; }
        info(int v_,int id_){ v=v_,id=id_; }
        inline bool operator>(const info& o)const{ return v>o.v; }
        inline bool operator<(const info& o)const{ return v<o.v; }
    }v[N],mx[N],cmx[N];
    inline void ad(info& mx,info& cmx,const info& x){
        if(x>mx){ cmx=mx;mx=x; }
        else if(mx>x && x>cmx){ cmx=x; }
    }

    #define ls ch[u][0]
    #define rs ch[u][1]
    inline int get(int u){ return ch[fa[u]][1]==u; }
    inline bool isrt(int u){ return fa[u]==0 || ( ch[fa[u]][0]!=u && ch[fa[u]][1]!=u ); }
    inline void pushup(int u){
        mx[u]=v[u];
        cmx[u].v=-inf;cmx[u].id=-1;
        // ad(mx[u],cmx[u],mx[ls]);
        // ad(mx[u],cmx[u],cmx[ls]);
        // ad(mx[u],cmx[u],mx[rs]);
        // ad(mx[u],cmx[u],cmx[rs]);
        mx[u]=max(mx[u],max(mx[ls],mx[rs]));
    }
    inline void pushdown(int u){
        if(iv[u]){
            iv[u]=0; swap(ls,rs);
            if(ls) iv[ls]^=1;
            if(rs) iv[rs]^=1;
        }
    }
    void upd(int u){
        if(!isrt(u)) upd(fa[u]);
        pushdown(u);
    }

    void rotate(int u){
        int v=fa[u],w=fa[v],c=get(u);
        if(!isrt(v)){ ch[w][ch[w][1]==v]=u; }
        ch[v][c]=ch[u][c^1];fa[ch[u][c^1]]=v;ch[u][c^1]=v;
        fa[v]=u;fa[u]=w;
        pushup(v),pushup(u);
    }
    void splay(int u){ upd(u); for(int f;f=fa[u],!isrt(u);rotate(u)){ if(!isrt(f)) rotate((get(f)==get(u))?f:u); } }
    inline void access(int u){ for(int l=0;u;l=u,u=fa[u]){ splay(u);ch[u][1]=l;pushup(u); } }
    inline int findrt(int u){ access(u);splay(u); while(pushdown(u),ls) u=ls; pushdown(u); splay(u);return u; }
    inline void makert(int u){ access(u);splay(u);iv[u]^=1;pushdown(u); }
    inline void split(int u,int v){ makert(u);access(v);splay(v); }
    inline void link(int u,int v){ makert(u);fa[u]=v; }
    inline void cut(int u,int v){ split(u,v);fa[u]=ch[v][0]=0;pushup(v); }
    inline bool chk(int u,int v){ makert(u);return findrt(v)==u; }

}
using namespace Cms;

int n,m;
struct edge{
    int x,y;ll z;
}E[300005];

int fat[300005];
int getfa(int u){
    return (fat[u]==u)?u:(fat[u]=getfa(fat[u]));
}

int main(){

    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++) fat[i]=i;
    for(int i=1;i<=m;i++){
        // int x,y,z;cin>>x>>y>>z;if(x>y) swap(x,y);
        // if(x==y) continue;
        // auto t=make_pair(x,y);
        // if(mp.count(t)) mp[t]=min(mp[t],ll(z));
        // else mp[t]=z;
        cin>>E[i].x>>E[i].y>>E[i].z;
        v[i+n].v=E[i].z;v[i+n].id=i;pushup(i+n);
    }
    // m=0;
    // for(auto& i:mp){
    //     E[++m].x=i.first.first;
    //     E[m].y=i.first.second;
    //     E[m].z=i.second;
    //     // cout<<i.second<<endl;
    //     v[m+n].v=E[m].z;v[m+n].id=m;pushup(m+n);
    // }

    ll tot=0;
    for(int i=1;i<=m;i++){
        int u=E[i].x,v=E[i].y;ll w=E[i].z;
        fat[getfa(u)]=getfa(v);
        // cout<<u<<" "<<v<<" "<<w<<" "<<i+n<<endl;
        if(!chk(u,v)){
            link(u,i+n);link(i+n,v);tot+=w;
            // cout<<"-- Lk "<<u<<" "<<v<<endl;
        }else{
            split(u,v);
            if(mx[v].v>w){
                int cu=mx[v].id;
                tot-=E[cu].z;tot+=w;
                // cout<<"-- C "<<E[cu].x<<" "<<E[cu].y<<endl;
                // cout<<"-- L "<<u<<" "<<v<<endl;
                cut(E[cu].x,mx[v].id+n);
                cut(mx[v].id+n,E[cu].y);
                link(u,i+n);link(i+n,v);
            }
        }
    }
    int cnt=0;
    for(int i=1;i<=n;i++) if(fat[i]==i) cnt++;
    if(cnt==1) cout<<tot<<"\n";
    else cout<<"orz\n";

    // while(m--){
    //     int op,x,y;
    //     cin>>op>>x>>y;
    //     if(op==0){
    //         split(x,y);cout<<s[y]<<"\n";
    //     }else if(op==1){
    //         if(findrt(x)==findrt(y)) continue;
    //         link(x,y);
    //     }else if(op==2){
    //         cut(x,y);
    //     }else{
    //         makert(x);v[x]=y;pushup(x);
    //     }
    // }

    return 0;
}