我们发现，这个染色的操作他就很像LCT中access的操作（为什么？？），然后就自然而然地想到，其实一个某条路径上的颜色数量，就是我们做一个只有access操作的LCT，这条路径经过的splay的数量
然后考虑怎么样来维护这个数量。access的过程中，有实边变虚边、虚边变实边的操作，对应过来，实边变虚边，就是以（断掉的那个子splay树中的在原树中最浅的点）为根的子树中 每个点到根的颜色数++（多拆出来了一个splay嘛），虚边变实边同理，不过是--
这样就可以再用一个线段树维护dfs序了，第三个询问就是线段树上的最大值
第二个询问，如果有x,y,lca，那x到y路径上的颜色数就是num[x]+num[y]-2*num[lca]+1，num[i]就是刚才线段树记的那个
#include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1e5+; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N,M;
int eg[maxn*][],egh[maxn],ect;
int dep[maxn],dfn[maxn][],fa[maxn],ch[maxn][],tot;
int bf[maxn][],ma[maxn*],laz[maxn*],id[maxn]; inline void adeg(int a,int b){
eg[++ect][]=b,eg[ect][]=egh[a];egh[a]=ect;
} void dfs(int x){
dfn[x][]=++tot;id[tot]=x;
for(int i=;bf[x][i]&&bf[bf[x][i]][i];i++)
bf[x][i+]=bf[bf[x][i]][i];
for(int i=egh[x];i;i=eg[i][]){
int b=eg[i][];
if(b==fa[x]) continue;
fa[b]=bf[b][]=x;dep[b]=dep[x]+;
dfs(b);
}
dfn[x][]=tot;
} inline int getlca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=log2(dep[x]-dep[y]);i>=&&dep[x]!=dep[y];i--){
if(dep[bf[x][i]]>=dep[y])
x=bf[x][i];
}
if(x==y) return x;
for(int i=log2(dep[x]);i>=;i--){
if(bf[x][i]!=bf[y][i])
x=bf[x][i],y=bf[y][i];
}
return bf[x][];
} inline bool nroot(int x){return x==ch[fa[x]][]||x==ch[fa[x]][];}
inline bool isrt(int x){return x==ch[fa[x]][];} inline void rotate(int x){
int f=fa[x],ff=fa[fa[x]];bool b=isrt(x);
fa[x]=ff;if(nroot(f)) ch[ff][isrt(f)]=x;
fa[ch[x][!b]]=f,ch[f][b]=ch[x][!b];
fa[f]=x,ch[x][!b]=f;
} inline void splay(int x){
while(nroot(x)&&nroot(fa[x])){
if(isrt(x)==isrt(fa[x])) rotate(fa[x]);
else rotate(x);rotate(x);
}if(nroot(x)) rotate(x);
} inline int getl(int x){
while(ch[x][]) x=ch[x][];
return x;
} inline void update(int p){ma[p]=max(ma[p<<],ma[p<<|]);}
inline void pushdown(int p){
if(!laz[p]) return;
int a=p<<,b=p<<|;
laz[a]+=laz[p],laz[b]+=laz[p];
ma[a]+=laz[p],ma[b]+=laz[p];
laz[p]=;
} inline void build(int p,int l,int r){
if(l==r) ma[p]=dep[id[l]];
else{
int m=l+r>>;
build(p<<,l,m);
build(p<<|,m+,r);
update(p);
}
}
inline void add(int p,int l,int r,int x,int y,int z){
// printf("%d %d %d %d %d\n",p,l,r,x,y);
if(x<=l&&r<=y){
ma[p]+=z;laz[p]+=z;
}else{
pushdown(p);
int m=l+r>>;
if(x<=m) add(p<<,l,m,x,y,z);
if(y>=m+) add(p<<|,m+,r,x,y,z);
update(p);
}
}
inline int query(int p,int l,int r,int x,int y){
if(!x||!y) return ;
if(x<=l&&r<=y) return ma[p];
pushdown(p);
int m=l+r>>,re=;
if(x<=m) re=query(p<<,l,m,x,y);
if(y>=m+) re=max(re,query(p<<|,m+,r,x,y));
return re;
} inline void access(int x){
for(int y=;x;y=x,x=fa[x]){
splay(x);
int a=getl(ch[x][]),b=getl(y);
// printf("!%d %d\n",a,b);
if(a) add(,,N,dfn[a][],dfn[a][],);
if(b) add(,,N,dfn[b][],dfn[b][],-);
ch[x][]=y;
}
} inline int gettop(int x){
while(nroot(x)) x=fa[x];
return x;
} int main(){
//freopen("","r",stdin);
int i,j,k;
N=rd(),M=rd();
for(i=;i<N;i++){
int a=rd(),b=rd();
adeg(a,b);adeg(b,a);
}
dep[]=;dfs();
build(,,N);
for(i=;i<=M;i++){
int a=rd(),x=rd();
if(a==) access(x);
else if(a==){
int y=rd();
int lca=getlca(x,y);
// printf("%d %d\n",x,y)
printf("%d\n",query(,,N,dfn[x][],dfn[x][])+
query(,,N,dfn[y][],dfn[y][])-
*query(,,N,dfn[lca][],dfn[lca][])+);
}else{
printf("%d\n",query(,,N,dfn[x][],dfn[x][]));
}
}
return ;
}