题解 P5489 【EntropyIncreaser 与 动态图】

· · 题解

更好的阅读体验 -> 推销博客

前言

这个题其实没有多难，静下来慢慢写还是十分可做的，不失为一道 \text{LCT} 练手好题。

正文

首先看到 1 操作连边，第一反应应该就是 \text{Link/Cut Tree} 了，然而怎么维护割边割点数量呢？我们分开讨论。

割边

考虑对于一个环，环上所有边一定不会是割边；而对于一条链，链上所有边一定是割边。

我们可以直接维护每条边是不是割边，初始时所有边都是割边，当某次加边操作产生了环，则环上所有边都不会成为割边了。

具体来讲，边转点后所有边权值均为 1 ，当某次 \text{Link} 的两结点已经连通，则将两结点间的链上的边全部赋值为 0 ，同时维护和即可。

割点

割点不像割边那样好处理了。

考虑静态的情况，静态割点有一个比较套路的方法是用圆方树，我们可以尝试动态地维护一棵圆方树：每次连边产生环就将环上所有点连到一个方点上来。

考虑这样做的复杂度：

假设环的长度是 L ，每次会用 O(L\log n) 的复杂度删去一个长为 O(L) 的环，均摊复杂度为 O(n\log n) 。

最后

于是使用两棵 \text{LCT} 分别维护割边和割点即可。

参考代码：

#include <cstdio>

#define N 200010
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]

inline void swap(int&a,int&b) {
    int tmp(a); a=b,b=tmp;
}

namespace Summer {
    int ch[N][2],fa[N],rev[N],val[N],sumv[N],mark[N];
    inline void reverse(int x) {
        if(x) {
            swap(lc(x),rc(x));
            rev[x]^=1;
        }
    }
    inline void NaCly_Fish_Orz(int x) {
        if(x) {
            val[x]=sumv[x]=0;
            mark[x]=1;
        }
    }
    inline void up(int x) {
        sumv[x]=sumv[lc(x)]+sumv[rc(x)]+val[x];
    }
    inline void down(int x) {
        if(rev[x]) {
            reverse(lc(x));
            reverse(rc(x));
            rev[x]=0;
        }
        if(mark[x]) {
            NaCly_Fish_Orz(lc(x));
            NaCly_Fish_Orz(rc(x));
            mark[x]=0;
        }
    }
    inline int nrt(int x) {
        return x==lc(fa[x])||x==rc(fa[x]);
    }
    void psa(int x) {
        if(nrt(x)) psa(fa[x]);
        down(x);
    }
    inline void rotate(int x) {
        int y(fa[x]),z(fa[y]),k(x==rc(y));
        ch[y][k]=ch[x][k^1],ch[x][k^1]=y;
        if(nrt(y)) ch[z][y==rc(z)]=x;
        if(ch[y][k]) fa[ch[y][k]]=y;
        fa[y]=x,fa[x]=z,up(y);
    }
    inline void splay(int x) {
        int y,z;
        for(psa(x);nrt(x);rotate(x)) {
            y=fa[x],z=fa[y];
            if(nrt(y)) rotate(x==rc(y)^y==rc(z)?x:y);
        } up(x);
    }
    inline void access(int x) {
        for(int y=0;x;x=fa[y=x]) {
            splay(x); rc(x)=y; up(x);
        }
    }
    inline void mrt(int x) {
        access(x); splay(x); reverse(x);
    }
    inline void link(int x,int y) {
        mrt(x); fa[x]=y;
    }
    inline void cut(int x,int y) {
        mrt(x); access(y); splay(y);
        fa[x]=lc(y)=0; up(y);
    }
}

namespace Pockets {
    int ch[N][2],fa[N],rev[N],val[N],sumv[N],st[N],num;
    inline void reverse(int x) {
        if(x) {
            swap(lc(x),rc(x));
            rev[x]^=1;
        }
    }
    inline void up(int x) {
        sumv[x]=sumv[lc(x)]+sumv[rc(x)]+val[x];
    }
    inline void down(int x) {
        if(rev[x]) {
            reverse(lc(x));
            reverse(rc(x));
            rev[x]=0;
        }
    }
    inline int nrt(int x) {
        return x==lc(fa[x])||x==rc(fa[x]);
    }
    void psa(int x) {
        if(nrt(x)) psa(fa[x]);
        down(x);
    }
    inline void rotate(int x) {
        int y(fa[x]),z(fa[y]),k(x==rc(y));
        ch[y][k]=ch[x][k^1],ch[x][k^1]=y;
        if(nrt(y)) ch[z][y==rc(z)]=x;
        if(ch[y][k]) fa[ch[y][k]]=y;
        fa[y]=x,fa[x]=z,up(y);
    }
    inline void splay(int x) {
        int y,z;
        for(psa(x);nrt(x);rotate(x)) {
            y=fa[x],z=fa[y];
            if(nrt(y)) rotate(x==rc(y)^y==rc(z)?x:y);
        } up(x);
    }
    inline void access(int x) {
        for(int y=0;x;x=fa[y=x]) {
            splay(x); rc(x)=y; up(x);
        }
    }
    inline void mrt(int x) {
        access(x); splay(x); reverse(x);
    }
    inline void link(int x,int y) {
        mrt(x); fa[x]=y;
    }
    inline void cut(int x,int y) {
        mrt(x); access(y); splay(y);
        fa[x]=lc(y)=0; up(y);
    }
    void print(int now) {
        if(now) {
            down(now);
            print(lc(now));
            st[++num]=now;
            print(rc(now));
        }
    }
}

int n,q,opt,u,v,last,tot,ans,SummerPockets;

int fa[N];
inline int find(int x) {
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

inline void getEdge(int u,int v) {
    int x=find(u),y=find(v);
    if(x!=y) {
        ans=-1;
        return;
    }
    Summer::mrt(u);
    Summer::access(v);
    Summer::splay(v);
    ans=Summer::sumv[v];
}

inline void getPoint(int u,int v) {
    int x=find(u),y=find(v);
    if(x!=y) {
        ans=-1;
        return;
    }
    Pockets::mrt(u);
    Pockets::access(v);
    Pockets::splay(v);
    ans=Pockets::sumv[v];
}

inline void link(int u,int v) {
    int x=find(u),y=find(v);
    if(x==y) {
        Summer::mrt(u);
        Summer::access(v);
        Summer::splay(v);
        Summer::NaCly_Fish_Orz(v);

        getPoint(u,v);
        if(ans>2) {
            ++SummerPockets;
            Pockets::mrt(u);
            Pockets::access(v);
            Pockets::splay(v);
            Pockets::num=0;
            Pockets::print(v);
            for(int i=1;i<Pockets::num;++i)
                Pockets::cut(Pockets::st[i],Pockets::st[i+1]);
            for(int i=1;i<=Pockets::num;++i)
                Pockets::link(Pockets::st[i],SummerPockets);
        }
    } else {
        ++tot; fa[y]=x;
        Summer::val[tot]=1;
        Summer::link(u,tot);
        Summer::link(tot,v);

        Pockets::link(u,v);
    }
}

int main() {
    scanf("%d%d",&n,&q);
    tot=SummerPockets=n;
    for(int i=1;i<=n;++i)
        fa[i]=i,Pockets::val[i]=1;
    while(q--) {
        scanf("%d%d%d",&opt,&u,&v);
        u^=last,v^=last;
        switch(opt) {
            case 1: {
                link(u,v);
                break;
            }
            case 2: {
                getEdge(u,v);
                if(ans!=-1) last=ans;
                printf("%d\n",ans);
                break;
            }
            default: {
                getPoint(u,v);
                if(ans!=-1) last=ans;
                printf("%d\n",ans);
                break;
            }
        }
    }
    return 0;
}