題目：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

總結

以上是生活随笔為你收集整理的bzoj2049 [Sdoi2008]Cave 洞穴勘测——LCT的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。