題目:https://www.lydsy.com/JudgeOnline/problem.php?id=2049
第二道LCT!
這題是模闆題,寫了一遍以後感覺對LCT的認識又加深了。
代碼如下:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int const maxn=10005,maxm=200005;
int n,m,c[maxn][3],rev[maxn],pre[maxn];
int rd()
{
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
void reverse(int x)
{
if(rev[x])
{
rev[c[x][0]]^=1; rev[c[x][1]]^=1;
swap(c[x][0],c[x][1]);
rev[x]=0;
}
}
bool isroot(int x)
{
return c[pre[x]][0]!=x && c[pre[x]][1]!=x;
}
void rotate(int x)
{
int y=pre[x],z=pre[y],d=(c[y][1]==x);
if(!isroot(y))c[z][c[z][1]==y]=x;
pre[x]=z; pre[y]=x;
c[y][d]=c[x][!d]; pre[c[x][!d]]=y; c[x][!d]=y;
}
void splay(int x)
{
int sta[maxn],top;
sta[top=1]=x;
for(int p=x;!isroot(p);p=pre[p])sta[++top]=pre[p];
for(;top;top--)reverse(sta[top]);
for(;!isroot(x);rotate(x))
{
int y=pre[x],z=pre[y];
if(isroot(y))continue;
((c[y][1]==x)^(c[z][1]==y))?rotate(x):rotate(y);
}
}
void access(int x)
{
for(int t=0;x;c[x][1]=t,t=x,x=pre[x]) splay(x);
}
void makeroot(int x)
{
access(x); splay(x); rev[x]^=1;
}
void link(int x,int y)
{
makeroot(x); pre[x]=y;
// splay(x);?
}
void query(int x,int y)
{
makeroot(x); access(y); splay(y);
}
void cut(int x,int y)
{
query(x,y);
pre[x]=0; c[y][0]=0;//access(y) 後 y 為 x 右兒子
}
int find(int x)//找到 x 所在樹的根節點
{
access(x); splay(x);
int y=x;
while(c[y][0])y=c[y][0];
return y;
}
int main()
{
n=rd(); m=rd();
char ch[10];int x,y;
while(m--)
{
scanf("%s",&ch);
x=rd(); y=rd();
if(ch[0]=='Q')
{
if(find(x)==find(y))printf("Yes\n");
else printf("No\n");
}
if(ch[0]=='C')link(x,y);
if(ch[0]=='D')cut(x,y);
}
return 0;
}
轉載于:https://www.cnblogs.com/Zinn/p/9196745.html