RT

思路：根号分治。

WA 成了 55 分。

按理来说肯定不可能 WA。。。

#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
	re int t=0;re char v=getchar();
	while(v<'0')v=getchar();
	while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
	return t;
}
int n,m,du[100002],head[100002],cnt,top[100002],dep[100002],vis[100002],son[100002],siz[100002],tim,fa[100002],vis1[100002],tag[100002],zzz,yy;
queue<int>q[2];
vector<int>v;
struct edge{int to,next;}e[200002];
inline void add(re int x,re int y){e[++cnt]=(edge){y,head[x]};head[x]=cnt;++du[x];}
inline void dfs1(re int x,re int y){
	fa[x]=y,siz[x]=1,dep[x]=dep[y]+1;
	for(re int i=head[x];i;i=e[i].next)
		if(e[i].to^y){
			dfs1(e[i].to,x);
			siz[x]+=siz[e[i].to];
			if(siz[e[i].to]>siz[son[x]])son[x]=e[i].to;
		}
}
inline void dfs2(re int x,re int y){
	top[x]=y;
	if(son[x])dfs2(son[x],y);
	for(re int i=head[x];i;i=e[i].next)if((e[i].to^fa[x])&&(e[i].to^son[x]))dfs2(e[i].to,e[i].to);
}
inline int lca(re int x,re int y){
	while(top[x]^top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}
inline int dis(re int x,re int y){
	return dep[x]+dep[y]-(dep[lca(x,y)]<<1);
}
inline void kz(){
	while(!q[zzz].empty()){
		re int x=q[zzz].front();q[zzz].pop();
		if(tag[x])continue;
		for(re int i=head[x];i;i=e[i].next){
			re int y=e[i].to;
		if(vis1[y]<tim)q[zzz^1].push(y),vis1[y]=vis1[x],vis[y]=vis[x]+1;
		}
	}
	zzz^=1;
}
inline int ask(re int x){
	if(vis1[x]>=tim)return 0;
	for(re int i=0;i<v.size();++i){
		if(vis1[v[i]]>=tim){
			if(dis(v[i],x)+vis[v[i]]<yy)return 0;
		}
	}
	return 1;
}
signed main(){
//	system("fc a.out tgT3.out");
	n=read(),m=read();
	for(re int i=1,x,y;i<n;++i){
		x=read(),y=read();
		add(x,y),add(y,x);
	}
	re int xx=sqrt(n);
	for(re int i=1;i<=n;++i)if(du[i]>=xx)tag[i]=1,v.push_back(i);
	++tim;
	while(m--){
		re int opt=read(),x=read();++yy;
		if(opt==1){
			if(vis1[x]<tim)vis1[x]=tim,q[zzz].push(x),vis[x]=yy;
		}
		else if(opt==2){
			++tim;
			while(!q[zzz].empty())q[zzz].pop();
		}
		else{
			puts(ask(x)?"orzFsYo":"wrxcsd");
		}
		kz();
	}
}