[WC2006]水管局长（LCT）

[Luogu4172] [DarkBZOJ2594(数据加强版)]

倒着处理所有询问，于是删边变成了加边。

#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int INF=1e9+7;
inline LL read(){
    register LL x=0,f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f*x;
}

const int MAXN=2e6+5;

struct Edge{ int x,y,w; } bian[MAXN];
inline bool cmp(Edge a,Edge b){ return a.w<b.w; }
struct Query{ int op,x,y,id; } q[MAXN];
bool del[MAXN];

int ans[MAXN];
int n,m,Q;
map <pii,int> Id;

namespace LCT{
    int ch[MAXN][2],fa[MAXN],maxid[MAXN],val[MAXN];
    int st[MAXN],top;
    bool rev[MAXN];
#define ls (ch[rt][0])
#define rs (ch[rt][1])

    inline bool chk(int x){
        return ch[fa[x]][1]==x;
    }

    inline bool isnotroot(int x){
        return ch[fa[x]][0]==x||ch[fa[x]][1]==x;
    }

    inline void pushup(int rt){
        maxid[rt]=val[rt];
        if(bian[maxid[ls]].w>bian[maxid[rt]].w) maxid[rt]=maxid[ls];
        if(bian[maxid[rs]].w>bian[maxid[rt]].w) maxid[rt]=maxid[rs];
    }

    inline void pushdown(int rt){
        if(!rev[rt]) return;
        rev[ls]^=1,rev[rs]^=1;
        swap(ch[ls][0],ch[ls][1]);
        swap(ch[rs][0],ch[rs][1]);
        rev[rt]=0;
    }

    inline void rotate(int x){
        int y=fa[x],z=fa[y],k=chk(x),w=ch[x][k^1];
        ch[y][k]=w,fa[w]=y;
        if(isnotroot(y)) ch[z][chk(y)]=x; fa[x]=z;
        ch[x][k^1]=y,fa[y]=x;
        pushup(y);pushup(x);
    }

    inline void splay(int x){
        int y=x,top=0;
        while(1){
            st[++top]=y;
            if(isnotroot(y)) y=fa[y];///
            else break;
        }
        while(top) pushdown(st[top--]);
        while(isnotroot(x)){
            int y=fa[x],z=fa[y];
            if(isnotroot(y)){
                if(chk(x)==chk(y)) rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
    }

    inline void access(int x){
        for(int y=0;x;x=fa[y=x])
            splay(x),ch[x][1]=y,pushup(x);
    }

    inline void makeroot(int x){
        access(x);splay(x);
        rev[x]^=1;
        swap(ch[x][0],ch[x][1]);
    }

    inline int findroot(int x){
        access(x);splay(x);
        while(ch[x][0]) pushdown(x),x=ch[x][0];
        splay(x);
        return x;
    }

    inline void link(int x,int y){
        makeroot(x);
        fa[x]=y;///这里的写法
    }

    inline void split(int x,int y){makeroot(x);access(y);splay(y);}
    inline void cut(int x,int y){split(x,y);fa[x]=ch[y][0]=0;}

}using namespace LCT;

int main(){
    n=read(),m=read(),Q=read();
    for(int i=1;i<=m;i++){
        bian[i].x=read(),bian[i].y=read(),bian[i].w=read();
        if(bian[i].x>bian[i].y) swap(bian[i].x,bian[i].y);
    }
    sort(bian+1,bian+m+1,cmp);
    for(int i=1;i<=m;i++) Id[pii(bian[i].x,bian[i].y)]=i;
    for(int i=1;i<=Q;i++){
        q[i].op=read(),q[i].x=read(),q[i].y=read();
        if(q[i].x>q[i].y) swap(q[i].x,q[i].y);
        if(q[i].op==2){
            q[i].id=Id[pii(q[i].x,q[i].y)];
            del[q[i].id]=1;
        }
    }
    for(int i=n+1;i<=n+m;i++)
        maxid[i]=val[i]=i-n;

    for(int i=1,sum=0;i<=m;i++){
        if(del[i]) continue;
        if(sum==n-1) break;
        int x=bian[i].x,y=bian[i].y;
        if(findroot(x)!=findroot(y)){
            link(x,i+n);link(i+n,y);
            sum++;
        }
    }

    for(int i=Q;i>=1;i--){
        int x=q[i].x,y=q[i].y;
        if(q[i].op==1){
            split(x,y);
            ans[i]=bian[maxid[y]].w;
        }
        if(q[i].op==2){
            split(x,y);
            int t=maxid[y];
            if(bian[q[i].id].w<bian[t].w){
                cut(bian[t].x,t+n);cut(t+n,bian[t].y);
                link(x,q[i].id+n);link(q[i].id+n,y);
            }
        }
    }

    for(int i=1;i<=Q;i++)
        if(q[i].op==1) printf("%d\n",ans[i]);
}

[WC2006]水管局长（LCT）

原文：https://www.cnblogs.com/lizehon/p/10513416.html