BZOJ4668 冷战(LCT维护最小生成树)

BZOJ4668 冷战(LCT维护最小生成树)

题面

自己找去

HINT

这道题就是动态加边，然后查询u,v两点最早什么时候联通，强制在线。思考一下，最早什么时候联通不就等同于维护最小生成树吗（把这条边加入的时间视为边权），然后就动态维护一下最小生成树，有个小细节，如果两点不连通,lastans要更新成0，被这个坑了

tips

出题人其实是想放带权并查集过的，所以数据范围是\(5e5\)，如果把数据下载下来测是没法1s过大的点的，但是BZOJ是总时长，也就轻松AC了。

#include<bits/stdc++.h>
#define ls(x) st[x].ch[0]
#define rs(x) st[x].ch[1]
#define fa(x) st[x].f
using namespace std;
inline int read(){
    int w=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        w=(w<<3)+(w<<1)+ch-48;
        ch=getchar();
    }
    return w*f;
}
int n,m;
bool debug;
struct LINK_CUT_TREE{
    struct Node{
        int ch[2],f,maxx,val;
        bool rev;
    }st[2000010];
    inline bool identify(int x){
        return st[fa(x)].ch[1]==x;
    }
    inline void connect(int x,int fa,int son){
        st[x].f=fa;st[fa].ch[son]=x;return;
    }
    inline void pushup(int x){
        st[x].maxx=max(st[ls(x)].maxx,st[rs(x)].maxx);
        st[x].maxx=max(st[x].maxx,st[x].val);return;
    }
    inline void pushrev(int x){
        st[x].rev^=1;swap(ls(x),rs(x));return;
    }
    inline void pushdown(int x){
        if(st[x].rev){
            st[x].rev=0;
            if(ls(x))pushrev(ls(x));
            if(rs(x))pushrev(rs(x));
        }
    }
    inline bool isroot(int x){
        return st[fa(x)].ch[0]!=x&&st[fa(x)].ch[1]!=x;
    }
    inline void rotate(int x){
        int y=st[x].f;int z=st[y].f;int yson=identify(x);int zson=identify(y);
        int b=st[x].ch[yson^1];st[x].f=z;
        if(!isroot(y))connect(x,z,zson);
        connect(b,y,yson);connect(y,x,yson^1);
        pushup(y);pushup(x);return;
    }
    int sta[500010];
    inline void splay(int x){
        int y=x;int top=0;
        sta[++top]=y;
        while(!isroot(y))sta[++top]=y=fa(y);
        while(top)pushdown(sta[top--]);
        while(!isroot(x)){
            int y=st[x].f;
            if(!isroot(y)){
                if(identify(x)==identify(y)) rotate(x);
                else rotate(y);
            }
            rotate(x);
        }
    }
    inline void access(int x){
        int y=0;
        while(x){
            splay(x);rs(x)=y;pushup(x);y=x;x=fa(x);
        }
    }
    inline void makeroot(int x){
        access(x);splay(x);pushrev(x);return;
    }
    inline int findroot(int x){
        access(x);splay(x);
        while(ls(x)){
            pushdown(x);x=ls(x);
        }
        return x;
    }
    inline void split(int x,int y){
        makeroot(x);access(y);splay(y);return;
    }
    inline void link(int x,int y){
        makeroot(x);fa(x)=y;
    }
    inline void cut(int x,int y){
        makeroot(x);
        if(findroot(y)!=x||fa(x)!=y) return;
        ls(y)=fa(x)=0;pushup(x);pushup(y);return;
    }
}LCT;
int main(){
    n=read();m=read();int ans=0;int cur=0;
    //debug=true;
    for(int i=1;i<=m;i++){
        int opt=read();int x=read();int y=read();
        x=x^ans;y=y^ans;
        if(debug){
            cout<<"test:"<<x<<" "<<y<<endl;
        }
        if(opt==0){
            cur++;if(LCT.findroot(x)==LCT.findroot(y)) continue;
            LCT.st[i+n].val=cur;LCT.link(x,i+n);LCT.link(i+n,y);
        }
        else{
            if(LCT.findroot(x)!=LCT.findroot(y)){
                ans=0;puts("0");continue;
            }
            LCT.split(x,y);ans=LCT.st[y].maxx;printf("%d\n",ans);
        }
    }
    return 0;
}

BZOJ4668 冷战(LCT维护最小生成树)

原文：https://www.cnblogs.com/wenci/p/10645205.html