UOJ #207. 共价大爷游长沙 随机化+LCT维护子树信息

注意：$LCT$ 在 $link$ 的时候必须要 makeroot.  

假如要将 $y$ 连到 $x$ 上： 

如果只是将 $y$ Access 并 splay 然后直接连到 $x$ 上的话你会发现 $y$ 在 $splay$ 中所有左儿子其实都在 $(x,y)$ 之间，而这显然就不对了. 

code: 

#include <cstdio>
#include <string>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#define N 400006

using namespace std;

namespace IO {
    void setIO(string s)
    {
        string in=s+".in";
        string out=s+".out";
        freopen(in.c_str(),"r",stdin);
        freopen(out.c_str(),"w",stdout);
    }
};

namespace LCT {

    #define lson t[x].ch[0]
    #define rson t[x].ch[1]
    #define get(x) (t[t[x].f].ch[1]==x)
    #define IsR(x) (!(t[t[x].f].ch[0]==x||t[t[x].f].ch[1]==x))

    struct node {
        int sum,son,ch[2],rev,f;
    }t[N];
    int sta[N];

    inline void Pushup(int x)
    {
        t[x].sum=t[lson].sum^t[rson].sum^t[x].son;
    }

    inline void Mark(int x)
    {
        t[x].rev^=1;
        swap(lson,rson);
    }

    inline void Pushdown(int x)
    {
        if(t[x].rev)
        {
            t[x].rev^=1;
            if(lson) Mark(lson);
            if(rson) Mark(rson);
        }
    }

    inline void Rotate(int x)
    {
        int old=t[x].f,fold=t[old].f,which=get(x);
        if(!IsR(old)) t[fold].ch[t[fold].ch[1]==old]=x;
        t[old].ch[which]=t[x].ch[which^1],t[t[old].ch[which]].f=old;
        t[x].ch[which^1]=old,t[old].f=x,t[x].f=fold;
        Pushup(old),Pushup(x);
    }

    inline void Splay(int x)
    {
        int v=0,u=x,fa;
        for(sta[++v]=u;!IsR(u);u=t[u].f)  sta[++v]=t[u].f;
        for(;v;--v)  Pushdown(sta[v]);
        for(u=t[u].f;(fa=t[x].f)!=u;Rotate(x))
            if(t[fa].f!=u)
                Rotate(get(fa)==get(x)?fa:x);
    }

    void Access(int x)
    {
        for(int y=0;x;y=x,x=t[x].f)
        {
            Splay(x);
            t[x].son^=t[rson].sum;
            t[x].son^=t[y].sum;
            rson=y;
            Pushup(x);
        }
    }

    void Move_Root(int x)
    {
        Access(x);
        Splay(x);
        Mark(x);
    }

    int Find(int x)
    {
        Access(x);
        while(lson)  x=lson;
        return x;
    }

    void Link_Edge(int x,int y)
    {
        Move_Root(x);
        Move_Root(y);
        t[y].f=x;
        t[x].son^=t[y].sum;
        Pushup(x);
    }

    void Cut_Edge(int x,int y)
    {
        Move_Root(x);
        Access(y),Splay(y);
        t[t[y].ch[0]].f=0;
        t[y].ch[0]=0;
        Pushup(y);
    }

    void Update(int x,int v)
    {
        Access(x);
        Splay(x);
        t[x].son^=v;
        Pushup(x);
    }

    int query(int x,int y)
    {
        Move_Root(x);
        Access(y);
        return t[y].son;
    }

    #undef lson
    #undef rson

};

struct SS {
    int x,y,w;
    SS(int x=0,int y=0,int w=0):x(x),y(y),w(w){}
}S[N];

int n;

int main()
{
    srand(20011011);
    // IO::setIO("input");
    int i,j,m,tot=0,su=0;
    scanf("%d%d%d",&i,&n,&m);
    for(i=1;i<n;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        LCT::Link_Edge(x,y);
    }
    for(i=1;i<=m;++i)
    {
        int op;
        scanf("%d",&op);
        if(op==1)
        {
            int x,y,u,v;
            scanf("%d%d%d%d",&x,&y,&u,&v);
            LCT::Cut_Edge(x,y);
            LCT::Link_Edge(u,v);
        }
        if(op==2)
        {
            int x,y,w;
            scanf("%d%d",&x,&y);
            w=rand();
            S[++tot]=SS(x,y,w);
            LCT::Update(x,w);
            LCT::Update(y,w);
            su^=w;
        }
        if(op==3)
        {
            int x;
            scanf("%d",&x);
            LCT::Update(S[x].x,S[x].w);
            LCT::Update(S[x].y,S[x].w);
            su^=S[x].w;
        }
        if(op==4)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%s\n",LCT::query(x,y)==su?"YES":"NO");
        }
    }
    return 0;
}