<span>Luogu P4116 【Qtree3】</span>

我寻思这题为什么LCT题解这么少啊...
这个题目连换根都不要的话LCT岂不是不用维护翻转操作了嘛？
然后pushdown,makeroot等等函数都不要写了
然后50行就完事了？？？

#include <cstdio>
#define R register
const int MAXN=1e5+10;
int ch[MAXN][2],fa[MAXN],id[MAXN],co[MAXN];
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
inline int nroot(int x) { return ls(fa[x])==x||rs(fa[x])==x; }
inline int get(int x) { return x==rs(fa[x]); }
inline void update(int x) {
	id[x]=id[ls(x)]?id[ls(x)]:(co[x]?x:(id[rs(x)]?id[rs(x)]:0));
}
inline void rotate(int x) {
	int y=fa[x],z=fa[y],k=get(x),w=ch[x][!k];
	if(nroot(y)) ch[z][get(y)]=x;ch[x][!k]=y;ch[y][k]=w;
	if(w) fa[w]=y;fa[y]=x;fa[x]=z;update(x);update(y);
}
inline void splay(int x) {
	for(;nroot(x);rotate(x))
		if(nroot(fa[x])) rotate(get(x)^get(fa[x])?x:fa[x]);
}
inline void access(int x) {
	for(R int y=0;x;x=fa[y=x]) splay(x),rs(x)=y,update(x);
}
int n,q;
struct edge{ int y,next; }e[MAXN*2];
int cnt,head[MAXN];
inline void add(int x,int y) {
	e[++cnt].y=y;e[cnt].next=head[x];head[x]=cnt;
}
inline void dfs(int x,int fx) {
	fa[x]=fx;
	for(R int i=head[x];i;i=e[i].next) {
		if(e[i].y==fx)continue; dfs(e[i].y,x);
	}
}
int main(){
	scanf("%d%d",&n,&q);
	for(R int i=1;i<n;i++) {
		int x,y;scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	dfs(1,0);
	while(q--) {
		int x,y;
		scanf("%d%d",&x,&y);
		if(x==0) { splay(y);co[y]^=1;update(y); }
		else {
			access(y);splay(y);
			printf("%d\n",id[y]==0?-1:id[y]);
		}
	}
	return 0;
}

还挺快的，快读都不加就3s了