模板—数据结构—LCT

Code:

#include <cstdio>

#include <algorithm>

using namespace std;

#define N 300010

int fa[N],son[N][2],size[N],n,m;long long sum[N],num[N]; bool rev[N];

bool check(int p) {return son[fa[p]][1]==p;}

bool isroot(int p) {return son[fa[p]][0]!=p&&son[fa[p]][1]!=p;}

void pushup(int p) {if(p) size[p]=1+size[son[p][0]]+size[son[p][1]]

	,sum[p]=num[p]^sum[son[p][0]]^sum[son[p][1]];}

void pushdown(int p)

{

	if(!rev[p]) return; rev[p]=0;

	swap(son[son[p][0]][0],son[son[p][0]][1]),rev[son[p][0]]^=1;

	swap(son[son[p][1]][0],son[son[p][1]][1]),rev[son[p][1]]^=1;

}

void update(int p) {if(!isroot(p)) update(fa[p]);pushdown(p);}

void rotate(int p)

{

	int tmp1=fa[p],tmp2=fa[tmp1],tmp3=check(p);

	fa[son[tmp1][tmp3]=son[p][tmp3^1]]=tmp1,fa[p]=tmp2;

	if(!isroot(tmp1)) son[tmp2][check(tmp1)]=p;

	fa[son[p][tmp3^1]=tmp1]=p,pushup(tmp1),pushup(p);

}

void splay(int p)

{

	update(p);

	for(int i;i=fa[p],!isroot(p);rotate(p))

		if(!isroot(i)) rotate(check(p)==check(i)?i:p);

}

void access(int p) {for(int t=0;p;t=p,p=fa[p]) splay(p),son[p][1]=t,pushup(p);}

void makeroot(int p) {access(p),splay(p),rev[p]^=1,swap(son[p][0],son[p][1]);}

void link(int x,int y) {makeroot(x),access(y),splay(y),fa[x]=y;}

bool in_all(int x,int y)

{

	makeroot(x),access(y),splay(y);

	while((son[y][0]&&(!rev[y]))||(son[y][1]&&rev[y])) pushdown(y),y=son[y][0];

	return x==y;

}

void cut(int x,int y)

	{makeroot(x),access(y),splay(y);if(in_all(x,y)&&fa[x]==y&&son[y][0]==x&&(!son[x][1])) fa[x]=son[y][0]=0,pushup(y);}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++) scanf("%lld",&num[i]),sum[i]=num[i],size[i]=1;

	for(int i=1,opt,y;i<=m;i++)

	{

		long long x;

		scanf("%d%lld%d",&opt,&x,&y);

		if(opt==0) makeroot(x),access(y),splay(y),printf("%lld\n",sum[y]);

		else if(opt==1) {if(!in_all(x,y)) link(x,y);}

		else if(opt==2) cut(x,y);

		else makeroot(x),access(x),num[x]=y,pushup(x);

	}

}