( ext{Solution})
容易得出询问节点为 (v) 时，需要找出一个节点 (u) 符合 ( ext{dis}(u,v)le t_v-t_u)。
然后我就懵了，不知道该怎么处理。但其实很简单，我们的思路类似于树状数组，线段树之类优化的思路：平均查询与插入的时间复杂度。所以相当于将 (u) 的数据先插入，再用 (v) 来查询。
按照这个思路改写一下：(dep[u]+dep[v]-2 imes dep[ ext{LCA}(u,v)]le t_v-t_u)。
即 (dep[u]+t_u-2 imes dep[ ext{LCA}(u,v)]le t_v-dep[v])。
仔细思考一下这个不太好处理的 ( ext{LCA})，我们发现 (u) 的 ( ext{LCA}) 只会是 (u) 到根的链上的点，(v) 同理。我们可以用树剖来做这道题。
具体就是处理出 (dep[u]+t_u-2 imes dep[ ext{LCA}(u,v)]) 的最小值。存储每条链的 (maxd)（这个可以在线段树上计算），然后每插入一个 (u)，就更新其到根的链上的每一段的 (val) 值（即 (dep[u]+t_u)）。
查询就查到根的链上每一段的最小的 (dep[u]+t_u-2 imes dep[ ext{LCA}(u,v)]) 值即可。
( ext{Code})
#include <cstdio>
#define rep(i,_l,_r) for(signed i=(_l),_end=(_r);i<=_end;++i)
#define fep(i,_l,_r) for(signed i=(_l),_end=(_r);i>=_end;--i)
#define erep(i,u) for(signed i=head[u],v=to[i];i;i=nxt[i],v=to[i])
#define efep(i,u) for(signed i=Head[u],v=to[i];i;i=nxt[i],v=to[i])
#define print(x,y) write(x),putchar(y)
template <class T> inline T read(const T sample) {
T x=0; int f=1; char s;
while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
return x*f;
}
template <class T> inline void write(const T x) {
if(x<0) return (void) (putchar('-'),write(-x));
if(x>9) write(x/10);
putchar(x%10^48);
}
template <class T> inline T Max(const T x,const T y) {if(x>y) return x; return y;}
template <class T> inline T Min(const T x,const T y) {if(x<y) return x; return y;}
template <class T> inline T fab(const T x) {return x>0?x:-x;}
template <class T> inline T gcd(const T x,const T y) {return y?gcd(y,x%y):x;}
template <class T> inline T lcm(const T x,const T y) {return x/gcd(x,y)*y;}
template <class T> inline T Swap(T &x,T &y) {x^=y^=x^=y;}
#include <vector>
using namespace std;
const int maxn=1e5+5,inf=0x3f3f3f3f;
int maxd[maxn<<2],n,m,dfn[maxn],siz[maxn],f[maxn],dep[maxn],son[maxn],pos[maxn],Dfn,tp[maxn],ans[maxn<<2],val[maxn<<2];
vector <int> e[maxn];
bool tag[maxn<<2];
void dfs1(int u,int fa) {
siz[u]=1,f[u]=fa,dep[u]=dep[fa]+1;
for(int i=0;i<e[u].size();++i) {
int v=e[u][i];
if(v==fa) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[son[u]]<siz[v]) son[u]=v;
}
}
void dfs2(int u) {
pos[dfn[u]=++Dfn]=u;
if(son[u]) tp[son[u]]=tp[u],dfs2(son[u]);
for(int i=0;i<e[u].size();++i) {
int v=e[u][i];
if(v==f[u]||v==son[u]) continue;
tp[v]=v,dfs2(v);
}
}
void clear(int x) {ans[x]=val[x]=inf; tag[x]=1;}
void Delete(int x) {
if(tag[x]) clear(x<<1),clear(x<<1|1),tag[x]=0;
val[x<<1]=Min(val[x<<1],val[x]);
val[x<<1|1]=Min(val[x<<1|1],val[x]);
ans[x<<1]=Min(ans[x<<1],val[x<<1]-2*maxd[x<<1]);
ans[x<<1|1]=Min(ans[x<<1|1],val[x<<1|1]-2*maxd[x<<1|1]);
}
void pushUp(int u) {
if(!u) return;
ans[u]=Min(val[u]-2*maxd[u],Min(ans[u<<1],ans[u<<1|1]));
}
void modify(int o,int l,int r,int L,int R,int k) {
if(l>R||r<L) return;
if(l>=L&&r<=R) return (void) (ans[o]=Min(ans[o],(val[o]=Min(val[o],k))-2*maxd[o]));
int mid=l+r>>1;
Delete(o);
modify(o<<1,l,mid,L,R,k); modify(o<<1|1,mid+1,r,L,R,k);
pushUp(o);
}
void build(int o,int l,int r) {
ans[o]=val[o]=inf;
if(l==r) return (void) (maxd[o]=dep[pos[l]]);
int mid=l+r>>1;
build(o<<1,l,mid); build(o<<1|1,mid+1,r);
maxd[o]=Max(maxd[o<<1],maxd[o<<1|1]);
}
int query(int o,int l,int r,int L,int R) {
if(l>R||r<L) return inf;
if(l>=L&&r<=R) return ans[o];
int mid=l+r>>1;
Delete(o);
return Min(query(o<<1,l,mid,L,R),query(o<<1|1,mid+1,r,L,R));
}
void change(int u,int w) {
for(;u;u=f[tp[u]]) modify(1,1,n,dfn[tp[u]],dfn[u],w);
}
int ask(int u) {
int ret=inf;
for(;u;u=f[tp[u]]) ret=Min(ret,query(1,1,n,dfn[tp[u]],dfn[u]));
return ret;
}
int main() {
int u,v;
n=read(9),m=read(9);
rep(i,1,n-1) {
u=read(9),v=read(9);
e[u].push_back(v),e[v].push_back(u);
}
dfs1(1,0),tp[1]=1,dfs2(1); build(1,1,n);
rep(i,1,m) {
u=read(9),v=read(9);
if(u==1) change(v,dep[v]+i);
else if(u==2) clear(1);
else puts(ask(v)<=i-dep[v]?"wrxcsd":"orzFsYo");
}
return 0;
}