树剖+ODT

#include<bits/stdc++.h>
#define swap(x,y) x^=y^=x^=y
using namespace std;
const int N=5e5+5;
inline int read()
{
	int x(0);char c(0);
	for(;!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	return x;
}
int n,m,opt,u;
int head[N],nxt[N<<1],to[N<<1],cnt;
inline void addEdge(int u,int v)
{
	nxt[++cnt]=head[u];
	head[u]=cnt;
	to[cnt]=v;
}
namespace ODT
{
	struct Node
	{
		int l,r;
		mutable bool v;
		Node(int L,int R=-1,int V=0):l(L),r(R),v(V){}
		bool operator <(const Node x)const
		{
			return l<x.l;
		}
	};
	set<Node>s;
	inline auto split(int pos)
	{
		auto it=s.lower_bound(Node(pos));
		if(it!=s.end()&&it->l==pos)return it;
		it--;
		int l=it->l,r=it->r,v=it->v;
		s.insert(Node(l,pos-1,v));
		return s.insert(Node(pos,r,v)).first;
	}
	inline void assign(int l,int r,bool v)
	{
		auto itr=split(r+1),itl=split(l);
		s.erase(itl,itr);
		s.insert(Node(l,r,v));
	}
}
namespace Subdivision
{
	int fa[N],id[N],dep[N],son[N],siz[N],top[N];
	void dfs1(int u,int father)
	{
		dep[u]=dep[father]+1;
		fa[u]=father;
		siz[u]=1;
		for(int e=head[u];e;e=nxt[e])
		{
			int v=to[e];
			if(!dep[v]&&v!=father)
			{
				dfs1(v,u);
				siz[u]+=siz[v];
				if(!son[v]||siz[v]>siz[son[u]]) son[u]=v;
			}
		}
	}
	int tot;
	void dfs2(int u,int t)
	{
		top[u]=t;
		id[u]=++tot;
		if(!son[u])return;
		dfs2(son[u],t);
		for(int e=head[u];e;e=nxt[e])
		{
			int v=to[e];
			if(v!=fa[u]&&v!=son[u])
			{
				dfs2(v,v);
			}
		}
	}
}
using namespace Subdivision;
inline void change(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
		{
			swap(x,y);
		}
		ODT::assign(id[top[x]],id[x],0);
		x=fa[top[x]];
	}
	ODT::assign(min(id[x],id[y]),max(id[x],id[y]),0);
}
int main()
{
	n=read();
	ODT::s.insert(ODT::Node(1,n,0));
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		addEdge(x,y);
		addEdge(y,x);
	}
	dfs1(1,0);
	dfs2(1,1);
	m=read();
	while(m--)
	{
		opt=read();u=read();
		if(opt==1)
		{
			ODT::assign(id[u],id[u]+siz[u]-1,1);
		}
		else if(opt==2)
		{
			change(u,1);
		}
		else
		{
			putchar(ODT::split(id[u])->v+'0');
			putchar('\n');
		}
	}
	return 0;
}