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;
}
