BZOJ3637 Query on a tree VI

挺厉害的题

考虑用LCT分别维护黑森林和白森林，并维护子树大小

但是直接暴力link cut的话复杂度是跟度数相关的，就T了

那么我们维护有根森林，并保证在黑森林中每个连通块除了根一定是黑的，白森林中每个连通块除了根一定是白的（事实上我们会发现这样的话只有原树的根是不一定什么颜色的，对于其他的连通块的根，颜色一定是与这个连通块里其余的点不同的）

那么修改的时候就只需要把修改点与他的父亲之间在两个森林里分别link和cut，在查询的时候判断一下所在连通块的根与询问点是否同色即可，同色就是所在连通块的大小，不同色就是询问点所在的那个子树的大小

#include<iostream>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<map>
#include<bitset>
#include<set>
#include<stack>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 100010
#define MAXM 1010
#define ll long long
#define eps 1e-8
#define MOD 1000000007
#define INF 1000000000
struct vec{
	int to;
	int fro;
};
vec mp[MAXN*2];
int tai[MAXN],cnt;
int n,m;
int c[MAXN];
int FA[MAXN];
inline void be(int x,int y){
	mp[++cnt].to=y;
	mp[cnt].fro=tai[x];
	tai[x]=cnt;
}
inline void bde(int x,int y){
	be(x,y);
	be(y,x);
}
struct LCT{
	int fa[MAXN],son[MAXN][2],Siz[MAXN],siz[MAXN];
	inline void ud(int x){
		siz[x]=siz[son[x][0]]+siz[son[x][1]]+Siz[x]+1;
	}
	inline bool ir(int x){
		return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;
	}
	inline void cot(int x,int y,bool z){
		if(x){
			fa[x]=y;
		}
		if(y){
			son[y][z]=x;
		}
	}
	inline void rot(int x,bool z){
		int xx=fa[x],xxx=fa[xx];
		cot(son[x][z],xx,z^1);
		if(ir(xx)){
			fa[x]=xxx;
		}else{
			cot(x,xxx,son[xxx][1]==xx);
		}
		cot(xx,x,z);
		ud(xx);
	}
	void splay(int x){
		while(!ir(x)){
			int xx=fa[x],xxx=fa[xx];
			if(ir(xx)){
				rot(x,son[xx][0]==x);
			}else{
				bool z=son[xxx][0]==xx;
				if(son[xx][z]==x){
					rot(x,z^1);
					rot(x,z);
				}else{
					rot(xx,z);
					rot(x,z);
				}
			}
		}
		ud(x);
	}
	void splay(int x,int y){
		int xx=fa[x],xxx=fa[xx];
		while(xx!=y){
			if(xxx==y){
				rot(x,son[xx][0]==x);
			}else{
				bool z=son[xxx][0]==xx;
				if(son[xx][z]==x){
					rot(x,z^1);
					rot(x,z);
				}else{
					rot(xx,z);
					rot(x,z);
				}
			}
			xx=fa[x],xxx=fa[x];
		}
		ud(x);
	}
	void acs(int x){
		int t=0;
		while(x){
			splay(x);
			Siz[x]+=siz[son[x][1]];
			son[x][1]=t;
			Siz[x]-=siz[t];
			ud(x);
			t=x;
			x=fa[x];
		}
	}
	inline void link(int x){
		if(FA[x]){
			splay(x);
			acs(FA[x]);
			splay(FA[x]);
			fa[x]=FA[x];
			Siz[FA[x]]+=siz[x];
			ud(FA[x]);
		}
	}
	inline void cut(int x){
		if(FA[x]){
			acs(x);
			splay(FA[x]);
			splay(x,FA[x]);
			son[FA[x]][1]=0;
			fa[x]=0;
			ud(FA[x]);
		}
	}
	void ask(int x){
		acs(x);
		splay(x);
		int t=x;
		while(son[t][0]){
			t=son[t][0];
		}
		splay(t);
		if(c[t]==c[x]){
			printf("%d\n",siz[t]);
		}else{
			t=son[t][1];
			while(son[t][0]){
				t=son[t][0];
			}
			acs(t);
			printf("%d\n",Siz[t]+1);
		}
	}
};
LCT tre[2];
void dfs(int x){
	int i,y;
	for(i=tai[x];i;i=mp[i].fro){
		y=mp[i].to;
		if(y!=FA[x]){
			FA[y]=x;
			tre[1].link(y);
			dfs(y);
		}
	}
}
int main(){
	int i,x,y;
	scanf("%d",&n);
	for(i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		bde(x,y);
	}
	for(i=1;i<=n;i++){
		tre[0].siz[i]=tre[1].siz[i]=1;
		c[i]=1;
	}
	dfs(1);
	scanf("%d",&m);
	while(m--){
		scanf("%d%d",&y,&x);
		if(y==1){
			tre[c[x]].cut(x);
			tre[c[x]^=1].link(x);
		}
		if(y==0){
			tre[c[x]].ask(x);
		}
	}
	return 0;
}

/*
2
1 2
2
0 2
1 2

*/