本文共 1823 字，大约阅读时间需要 6 分钟。

第一道LCT的题目

就是模板

#include
   
    using namespace std;const int maxn=2e5;int n,m;struct lct{	struct node	{		int fa,ch[2],rev;		node() {fa=ch[0]=ch[1]=rev=0;}	}tree[maxn];	int top,res[maxn];	#define ls(x) tree[x].ch[0]	#define rs(x) tree[x].ch[1]	int isroot(int x) {return tree[x].fa && (ls(tree[x].fa)==x || rs(tree[x].fa)==x);}	void rev(int x)	{		swap(ls(x),rs(x));		tree[x].rev^=1;	}	void pushdown(int x)	{		if(!tree[x].rev) return ;		if(ls(x)) rev(ls(x));		if(rs(x)) rev(rs(x));		tree[x].rev^=1;	}	void rotate(int x)	{		int y=tree[x].fa,z=tree[y].fa;		int k=(x==ls(tree[x].fa)),w=tree[x].ch[k];		if(isroot(y)) tree[z].ch[y==rs(tree[y].fa)] =x;		tree[x].ch[k]=y; tree[y].ch[!k]=w;		tree[y].fa=x; tree[x].fa=z;		if(w) tree[w].fa=y;	}	void splay(int x)	{		int tmp=x;		res[top=1]=tmp;		while(isroot(tmp)) res[++top]=tree[tmp].fa,tmp=tree[tmp].fa;		while(top) pushdown(res[top]),top--;		while(isroot(x))		{			if(isroot(tree[x].fa)) rotate((x==rs(tree[x].fa))^(tree[x].fa==rs(tree[tree[x].fa].fa))?x:tree[x].fa);			rotate(x);		}	}	void access(int x)	{		for(int y=0;x;y=x,x=tree[x].fa)		{			splay(x); rs(x)=y;		}	}	void makeroot(int x)	{		access(x); splay(x); rev(x);	}	int findroot(int x)	{		access(x); splay(x); pushdown(x);		while(ls(x))		{			x=ls(x); pushdown(x);		 } 		 return x;	}	void link(int x,int y)	{		if(findroot(x)==findroot(y)) return;		makeroot(x); tree[x].fa=y;	}	void cut(int x,int y)	{		makeroot(x); access(y); splay(y);		if(ls(y)==x) tree[x].fa=ls(y)=0;	}}LCT;int main(){	freopen("a.in","r",stdin);	freopen("a.out","w",stdout);	scanf("%d%d",&n,&m);	char op[20];	int x,y;	for(int i=1;i<=m;i++)	{		scanf("%s",op);		scanf("%d%d",&x,&y);		if(op[0]=='C') LCT.link(x,y);		if(op[0]=='D') LCT.cut(x,y);		if(op[0]=='Q')		{			if(LCT.findroot(x)==LCT.findroot(y))				printf("Yes\n");			else printf("No\n");		}	}	return 0;}
   

转载地址：http://idwm.baihongyu.com/