[cogs2701]动态树

题面戳我

sol

比较裸啊。

注意操作顺序就行了。

code

#include<cstdio>

#include<algorithm>

using namespace std;

const int N = 200005;

int gi()

{

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

int n,q,fa[N],ls[N],rs[N],rev[N],sz[N],sum[N],Stack[N],top;

char s[1000];

bool isroot(int x){return ls[fa[x]]!=x&&rs[fa[x]]!=x;}

void pushup(int x){sum[x]=sum[ls[x]]+sum[rs[x]]+1+sz[x];}

void reverse(int x){swap(ls[x],rs[x]);rev[x]^=1;}

void pushdown(int x){if(!rev[x])return;if(ls[x])reverse(ls[x]);if(rs[x])reverse(rs[x]);rev[x]=0;}

void R_rotate(int x)

{

	int y=fa[x],z=fa[y];

	ls[y]=rs[x];

	if (rs[x]) fa[rs[x]]=y;

	fa[x]=z;

	if (y==ls[z]) ls[z]=x;if (y==rs[z]) rs[z]=x;

	rs[x]=y;fa[y]=x;

	pushup(y);

}

void L_rotate(int x)

{

	int y=fa[x],z=fa[y];

	rs[y]=ls[x];

	if (ls[x]) fa[ls[x]]=y;

	fa[x]=z;

	if (y==ls[z]) ls[z]=x;if (y==rs[z]) rs[z]=x;

	ls[x]=y;fa[y]=x;

	pushup(y);

}

void splay(int x)

{

	Stack[top=1]=x;

	for (int i=x;!isroot(i);i=fa[i])

		Stack[++top]=fa[i];

	while (top) pushdown(Stack[top--]);

	while (!isroot(x))

	{

		int y=fa[x],z=fa[y];

		if (isroot(y))

			if (x==ls[y]) R_rotate(x);

			else L_rotate(x);

		else

			if (y==ls[z])

				if (x==ls[y]) R_rotate(y),R_rotate(x);

				else L_rotate(x),R_rotate(x);

			else

				if (x==ls[y]) R_rotate(x),L_rotate(x);

				else L_rotate(y),L_rotate(x);

	}

	pushup(x);

}

void access(int x){for (int y=0;x;y=x,x=fa[x]) splay(x),sz[x]+=sum[rs[x]]-sum[y],rs[x]=y,pushup(x);}

void makeroot(int x){access(x);splay(x);reverse(x);}

int findroot(int x){access(x);splay(x);while (ls[x]) x=ls[x];return x;}

void link(int x,int y){makeroot(x);makeroot(y);fa[x]=y;sz[y]+=sum[x];pushup(y);}

int main()

{

	//freopen("dynamic_tree.in","r",stdin);

	//freopen("dynamic_tree.out","w",stdout);

	n=gi();q=gi();

	for (int i=1;i<=n;i++) sum[i]=1;

	while (q--)

	{

		int opt=gi(),u=gi();

		if (opt==1) makeroot(u);

		if (opt==2) access(u),printf("%d\n",sz[u]+1);

		if (opt==3) {int v=gi(),rt=findroot(u);link(u,v);makeroot(rt);}

	}

	return 0;

}