以最后被删去的点为根，这样子不会存在从父亲然后删掉某个点，儿子的删除顺序一定比父亲前。
记每个点子树中的最大值为 \(f_x\)，那么一个点的排名，首先就需要加上 \(<f_x\) 的所有值，记对应 \(f_x\) 的点为 \(y\)，那么 \(y\) 一定会一路上来删掉 \(x\)。
所以一个点排名就是 \(<f_x\) 的所有值，再加上 \(x,y\) 之间的距离。
考虑如何维护修改，设上一个根是 \(rt\)，新根是 \(x\)，那么等价于一次换根，需要将 \(x\) 到 \(rt\) 这条路径 cover 上 \(p_{rt}\)，同时改掉 \(x\) 的值。
可以使用 ODT + 树剖维护。
Code
const int N=2e5+5;
int n,m;
vi G[N];
int dep[N],siz[N],top[N],son[N],dfn[N],fat[N],dfc,p[N*2],rp[N*2];
void dfs1(int u,int fa) {
dep[u]=dep[fa]+1,siz[u]=1,fat[u]=fa;
for(int v:G[u]) if(v!=fa) {
dfs1(v,u),siz[u]+=siz[v];
p[u]=max(p[u],p[v]);
if(siz[son[u]]<siz[v]) son[u]=v;
}
}
void dfs2(int u,int tp,int fa) {
top[u]=tp,dfn[u]=++dfc;
if(son[u]==0) return;
dfs2(son[u],tp,u);
for(int v:G[u]) if(v!=fa&&v!=son[u]) dfs2(v,v,u);
}
int bit[2*N];
void add(int x,int v) { for(;x<=n+m;x+=(x&-x)) bit[x]+=v; }
int ask(int x) { int ret=0; for(;x;x-=(x&-x)) ret+=bit[x]; return ret; }
struct node {
int l,r,v;
node() {}
node(int L,int R,int V) { l=L,r=R,v=V; }
bool operator < (const node &a) const { return l<a.l; }
};
set<node> odt;
auto spilt(int p) {
auto it=odt.lower_bound(node(p,-1,0));
if(it!=odt.end()&&it->l==p) return it;
--it;
int l=it->l,r=it->r,v=it->v;
odt.erase(it),odt.insert(node(l,p-1,v));
return odt.insert(node(p,r,v)).fi;
}
void cover(int l,int r,int v) {
auto itr=spilt(r+1),itl=spilt(l);
for(auto it=itl;it!=itr;it=odt.erase(it)) add(it->v,-((it->r)-(it->l)+1));
add(v,r-l+1),odt.insert(node(l,r,v));
}
void update(int u,int v,int w) {
while(top[u]!=top[v]) {
if(dep[top[u]]<dep[top[v]]) swap(u,v);
cover(dfn[top[u]],dfn[u],w),u=fat[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
cover(dfn[u],dfn[v],w);
}
int lca(int u,int v) {
while(top[u]!=top[v]) {
if(dep[top[u]]<dep[top[v]]) swap(u,v);
u=fat[top[u]];
}
return dep[u]<dep[v]?u:v;
}
int dist(int u,int v) { return dep[u]+dep[v]-2*dep[lca(u,v)]+1; }
int query(int x) {
auto pos=odt.upper_bound(node(dfn[x],-1,0));
int val=prev(pos)->v;
return ask(val-1)+dist(x,rp[val]);
}
int main() {
n=read(),m=read();
FOR(i,1,n-1) {
int x=read(),y=read();
G[x].pb(y),G[y].pb(x);
}
FOR(i,1,n) p[i]=rp[i]=i;
int rt=n,mx=n;
dfs1(n,0),dfs2(n,n,0);
FOR(i,1,n) add(p[i],1),odt.insert(node(dfn[i],dfn[i],p[i]));
FOR(i,1,m) {
string ch; cin>>ch;
int u=read();
if(ch[0]=='1') {
if(u!=rt) update(rt,u,mx);
++mx,cover(dfn[u],dfn[u],mx),rp[mx]=rt=u;
}
else if(ch[0]=='2') printf("%d\n",query(u));
else { int v=read(); printf("%d\n",query(u)>query(v)?v:u);}
}
}