洛谷P3950 部落冲突 LCT

Code:

#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>



using namespace std;

void setIO(string a){
    freopen((a+".in").c_str(),"r",stdin);
}

#define maxn 300080

int n,m;
struct Link_Cut_Tree{

    int ch[maxn][2],f[maxn];
    int tag[maxn],sta[maxn];
    int get(int x)
    {
        return ch[f[x]][1]==x;
    }
    int which(int x)
    {
        return ch[f[x]][1]==x;
    }
    int isRoot(int x)
    {
        return !(ch[f[x]][1]==x||ch[f[x]][0]==x);
    }
    int lson(int x)
    {
        return ch[x][0];
    }
    int rson(int x)
    {
        return ch[x][1];
    }
    void mark(int x)
    {
        if(!x) return;
        swap(ch[x][0],ch[x][1]), tag[x]^=1;
    }
    void pushdown(int x)
    {
        if(tag[x]) mark(lson(x)), mark(rson(x)),tag[x]=0;
    }
    void rotate(int x)
    {
        int old=f[x],fold=f[old],which=get(x);
        if(!isRoot(old)) ch[fold][ch[fold][1]==old]=x;
        ch[old][which]=ch[x][which^1],f[ch[old][which]]=old;
        ch[x][which^1]=old,f[old]=x,f[x]=fold;
    }
    void splay(int x)
    {
        int v=0,u=x;
        sta[++v]=u;
        while(!isRoot(u)) sta[++v]=f[u],u=f[u];
        while(v) pushdown(sta[v--]);
        u=f[u];
        for(int fa;(fa=f[x])!=u;rotate(x))
            if(f[fa]!=u) rotate(get(fa)==get(x)?fa:x);
    }
    void Access(int x)
    {
        for(int y=0;x;y=x,x=f[x])
            splay(x),ch[x][1]=y;
    }
    void makeRoot(int x)
    {
        Access(x), splay(x), mark(x);
    }
    void link(int a,int b)
    {
        makeRoot(a), f[a]=b;
    }
    int findRoot(int a)
    {
        Access(a),splay(a);
        while(ch[a][0]) a=ch[a][0];
        return a;
    }
    void cut(int a,int b)
    {
        makeRoot(a),Access(b),splay(b);
        f[a]=ch[b][0]=0;
    }
    bool judge(int a,int b)
    {
        int x=findRoot(a),y=findRoot(b);
        if(x!=y)return true;
        return false;
    }
}tree;

int u[maxn],v[maxn],p;
int main()
{
    //setIO("input");
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;++i)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        tree.link(a,b);
    }
    char opt[20];
    int a,b;
    while(m--)
    {
        scanf("%s",opt);
        switch(opt[0])
        {
            case 'C': 
            {
                scanf("%d%d",&a,&b);
                u[++p]=a,v[p]=b;
                tree.cut(a,b);
                break;
            }
            case 'Q':
            {
                scanf("%d%d",&a,&b);
                bool ans=tree.judge(a,b);
                if(ans==0) printf("Yes
");
                else printf("No
");
                break;
            }
            case 'U':
            {
                scanf("%d",&a);
                tree.link(u[a],v[a]);
                break;
            }
        }
    }
    return 0;
}