考虑到每次都是到根染上一种和原来不同的颜色
这个操作和时的很像
实际询问的也就是到根改变了多少次虚实链
考虑一次的影响
对原来的实儿子也就是多了一次切换
子树答案加1就是了
对于新的实儿子则少了一个切换
子树答案减一
树剖维护一下就完了
#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<20|1;
inline char gc(){
static char ibuf[RLEN],*ib,*ob;
(ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
return (ob==ib)?EOF:*ib++;
}
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
int n,m;
const int N=100005;
namespace Seg{
int tr[N<<2],add[N<<2],idx[N],dep[N];
#define lc (u<<1)
#define rc ((u<<1)|1)
#define mid ((l+r)>>1)
inline void pushup(int u){
tr[u]=max(tr[lc],tr[rc]);
}
inline void pushnow(int u,int k){
tr[u]+=k,add[u]+=k;
}
inline void pushdown(int u){
if(!add[u])return;
pushnow(lc,add[u]);
pushnow(rc,add[u]);
add[u]=0;
}
void build(int u,int l,int r){
if(l==r){tr[u]=dep[idx[l]];return;}
build(lc,l,mid),build(rc,mid+1,r);
pushup(u);
}
void update(int u,int l,int r,int st,int des,int k){
if(st<=l&&r<=des)return pushnow(u,k);
pushdown(u);
if(st<=mid)update(lc,l,mid,st,des,k);
if(mid<des)update(rc,mid+1,r,st,des,k);
pushup(u);
}
int query(int u,int l,int r,int st,int des){
if(st<=l&&r<=des)return tr[u];
pushdown(u);
int res=0;
if(st<=mid)res=max(res,query(lc,l,mid,st,des));
if(mid<des)res=max(res,query(rc,mid+1,r,st,des));
pushup(u);return res;
}
#undef mid
#undef lc
#undef rc
}
using namespace Seg;
namespace SLPF{
int adj[N],nxt[N<<1],to[N<<1],in[N],siz[N],fa[N],top[N],son[N],dfn,cnt;
inline void addedge(int u,int v){
nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v;
}
void dfs1(int u){
siz[u]=1;
for(int e=adj[u];e;e=nxt[e]){
int v=to[e];
if(v==fa[u])continue;
dep[v]=dep[u]+1,fa[v]=u;
dfs1(v),siz[u]+=siz[v];
if(siz[v]>=siz[son[u]])son[u]=v;
}
}
void dfs2(int u,int tp){
in[u]=++dfn,idx[dfn]=u,top[u]=tp;
if(son[u])dfs2(son[u],tp);
for(int e=adj[u];e;e=nxt[e]){
int v=to[e];
if(v==fa[u]||v==son[u])continue;
dfs2(v,v);
}
}
inline int Lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
u=fa[top[u]];
}
return dep[u]>dep[v]?v:u;
}
}
using namespace SLPF;
namespace Lct{
int son[N][2],f[N];
#define lc(u) son[u][0]
#define rc(u) son[u][1]
inline bool isrt(int u){
if(!f[u])return 1;
return lc(f[u])!=u&&rc(f[u])!=u;
}
inline bool isrc(int u){
return rc(f[u])==u;
}
inline void rotate(int v){
int u=f[v],z=f[u];
int t=rc(u)==v;
if(!isrt(u))son[z][rc(z)==u]=v;
f[v]=z;
son[u][t]=son[v][t^1],f[son[v][t^1]]=u;
son[v][t^1]=u,f[u]=v;
}
inline void splay(int u){
while(!isrt(u)){
if(!isrt(f[u]))
isrc(f[u])==isrc(u)?rotate(f[u]):rotate(u);
rotate(u);
}
}
inline int findrt(int u){
while(lc(u))u=lc(u);return u;
}
inline void access(int u){
for(int v=0,z;u;v=u,u=f[u]){
splay(u);
if(rc(u))z=findrt(rc(u)),update(1,1,n,in[z],in[z]+siz[z]-1,1);
if(rc(u)=v)z=findrt(v),update(1,1,n,in[z],in[z]+siz[z]-1,-1);
}
}
#undef lc
#undef rc
}
int main(){
dep[1]=1;
n=read(),m=read();
for(int i=1;i<n;i++){
int u=read(),v=read();
addedge(u,v),addedge(v,u);
}
dfs1(1),dfs2(1,1);
build(1,1,n);
for(int i=1;i<=n;i++){
Lct::f[i]=fa[i];
}
while(m--){
int op=read(),u=read();
if(op==1)Lct::access(u);
if(op==2){
int v=read(),lca=Lca(u,v);
cout<<(query(1,1,n,in[u],in[u])+query(1,1,n,in[v],in[v])-2*query(1,1,n,in[lca],in[lca])+1)<<'
';
}
if(op==3){
cout<<query(1,1,n,in[u],in[u]+siz[u]-1)<<'
';
}
}
}