记录编号	412464	评测结果	AAAAAAAAAA
题目名称	动态树	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.472 s
提交时间	2017-06-09 14:24:33	内存使用	6.78 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int n,m,fa[N],son[N][2],v[N],pre[N],suf[N];
bool root[N];
int apre[N],asuf[N];bool rev[N];
//v[x]表示子树x大小减去pre_child子树的大小 
//pre,suf表示一颗splay上v的前缀后缀和 
#define lc son[x][0]
#define rc son[x][1]
void flip(int x){
	swap(lc,rc);
	swap(pre[x],suf[x]);
	swap(apre[x],asuf[x]);
	rev[x]^=1;
}
void add_pre(int x,int d){
	pre[x]+=d;
	apre[x]+=d;
}
void add_suf(int x,int d){
	suf[x]+=d;
	asuf[x]+=d;
}
void pushdown(int x){
	if (!x) return;
	if (rev[x]){
		if (lc) flip(lc);
		if (rc) flip(rc);
		rev[x]=0;
	}
	if (apre[x]){
		if (lc) add_pre(lc,apre[x]);
		if (rc) add_pre(rc,apre[x]);
		apre[x]=0;
	}
	if (asuf[x]){
		if (lc) add_suf(lc,asuf[x]);
		if (rc) add_suf(rc,asuf[x]);
		asuf[x]=0;
	}
}
void rot(int x){
	int y=fa[x],z=fa[y];
	bool b=(x==son[y][1]);
	fa[son[y][b]=son[x][!b]]=y;
	fa[son[x][!b]=y]=x;
	fa[x]=z;
	if (son[z][0]==y) son[z][0]=x;else
	if (son[z][1]==y) son[z][1]=x;
	root[x]=root[y];root[y]=0;
}
void splay(int x){
	pushdown(x);
	for (;!root[x];rot(x)){
		int y=fa[x],z=fa[y];
		pushdown(z);pushdown(y);pushdown(x);
		if (!root[y]) rot((x==son[y][0])==(y==son[z][0])?y:x);
	}
}
//suf[x]即子树x的大小 
int top(int x){
	for (;;x=lc){
		pushdown(x);
		if (!lc) break;
	}
	splay(x);
	return x;
}
void link_r(int x,int y){
	y=top(y);
	v[x]-=suf[y];
	pre[x]-=suf[y];
	add_pre(y,pre[x]);
	root[rc=y]=0;
}
void cut_r(int x){
	int y=rc;
	if (!y) return;
	root[rc]=1;rc=0;
	y=top(y);
	add_pre(y,-pre[x]);
	v[x]+=suf[y];
	pre[x]+=suf[y];
}
void access(int x){
	splay(x);
	cut_r(x);
	while (fa[x]){
		int y=fa[x];
		splay(y);
		cut_r(y);
		link_r(y,x);
		splay(x);
	}
}
void makeroot(int x){
	access(x);
	flip(x);
}
int main()
{
	freopen("dynamic_tree.in","r",stdin);
	freopen("dynamic_tree.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) pre[i]=suf[i]=v[i]=root[i]=1;
	while (m--){
		int tp,x,y;
		scanf("%d%d",&tp,&x);
		if (tp==1) makeroot(x);
		if (tp==2) splay(x),printf("%d\n",suf[x]);
		if (tp==3){
			scanf("%d",&y);
			makeroot(y);
			fa[y]=x;
			access(x);
			v[x]+=suf[y];
			pre[x]+=suf[y];
			add_suf(x,suf[y]);
		}
	}
	return 0;
}