Findstrなのです

lk砍树的板，记下来好了

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
#define PROC "2049"
using namespace std;
const int maxn=10100;
struct hja{
    hja *fa, *ch[2];
    bool tag;
     
    void gettag()
    {
        tag^=1;
    }
     
    void pushdown()
    {
        if (tag)
        {
            ch[1]->gettag();
            ch[0]->gettag();
            swap(ch[0],ch[1]);
            tag=0;
        }
    }
} rnil;
hja *nil=&rnil;
int n, m;
namespace LCT{
    hja tree[maxn];
    void init(hja &now)
    {
        now.ch[0]=now.ch[1]=now.fa=nil;
    }
    void init()
    {
        for (int i=1; i<=n; i++)
            init(tree[i]);
    }
    bool isRoot(hja *now)
    {
        return now->fa->ch[0]!=now&&now->fa->ch[1]!=now;
    }
    void rotate(hja *now)
    {
        hja *fa=now->fa;
        hja *gfa=fa->fa;
        bool d=fa->ch[1]==now;
        if (!isRoot(fa))
            gfa->ch[gfa->ch[1]==fa]=now;
        now->fa=gfa;
        fa->fa=now;
        fa->ch[d]=now->ch[d^1];
        now->ch[d^1]->fa=fa;
        now->ch[d^1]=fa;
    }
    stack<hja*> sta;
    void splay(hja *now)
    {
        hja *pre=now;
        sta.push(pre);
        while (!isRoot(pre))
        {
            pre=pre->fa;
            sta.push(pre);
        }
        while (!sta.empty())
        {
            sta.top()->pushdown();
            sta.pop();
        }
        while (!isRoot(now))
        {
            hja *fa=now->fa, *gfa=now->fa->fa;
            if (!isRoot(fa))
            {
                if ((gfa->ch[1]==fa)!=(fa->ch[1]==now))
                    rotate(now);
                else
                    rotate(fa);
            }
            rotate(now);
        }
    }
    void access(hja* nowp)
    {
        for (hja *son=nil; nowp!=nil; nowp=nowp->fa)
        {
            splay(nowp);
            nowp->ch[1]=son;
            son=nowp;
        }
    }
    void access(int nowp)
    {
        access(&tree[nowp]);
    }
 
    void makeRoot(hja* nowp)
    {
        access(nowp);
        splay(nowp);
        nowp->gettag();
    }
    void makeRoot(int nowp)
    {
        makeRoot(&tree[nowp]);
    }
    void cut(hja* p1, hja* p2)
    {
        makeRoot(p1);
        access(p2);
        splay(p2);
        p1->fa=nil;
        p2->ch[0]=nil;
    }
    void cut(int p1, int p2)
    {
        cut(&tree[p1],&tree[p2]);
    }
    hja* find(hja *p1)
    {
        access(p1);
        splay(p1);
        while (p1->ch[0]!=nil)
            p1=p1->ch[0];
        return p1;
    }
    int find(int nowp)
    {
        return find(&tree[nowp])-tree;
    }
    bool find(int p1, int p2)
    {
        return find(p1)==find(p2);
    }
    bool find(hja* p1, hja* p2)
    {
        return find(p1)==find(p2);
    }
    void link(hja* p1, hja* p2)
    {
        makeRoot(p1);
        p1->fa=p2;
        access(p1);
    }
    void link(int p1, int p2)
    {
        link(&tree[p1],&tree[p2]);
    }
}
 
char s[10];
 
int main()
{
#ifdef YJQ_LOCAL
    freopen(PROC".in","r",stdin);
//  freopen(PROC".out","w",stdout);
#endif
    int tmp1,tmp2,tmp3;
    scanf("%d%d",&n,&m);
    LCT::init();
    while(m--)
    {
        scanf("%s%d%d",s+1,&tmp1,&tmp2);
        if (s[1]=='Q')
            puts(LCT::find(tmp1,tmp2)?"Yes":"No");
        if (s[1]=='C')
            LCT::link(tmp1,tmp2);
        if (s[1]=='D')
            LCT::cut(tmp1,tmp2);
    }
    fclose(stdout);
    return 0;
}