Solution
考虑用(LCT)维护颜色。每一个(splay)维护的是两两不同的颜色。
第一个操作可以实际上就是(access)操作。
第二个操作问路径上的颜色种类数。第三个问子树内颜色种类的(max)。
因为是静态树，不能再把路径(split)出来了。考虑差分回答：(ans=cnt[a]+cnt[b]-2 imes cnt[lca(a,b)]+1)。
而(cnt[])实际上就是点到根路径上的(splay)的数量，也是虚边数量+1。
初始时(cnt[])就是该点深度。因为是静态树，没有(link)，所以改变虚边情况的只有(access)。
(access)操作中每向上走一个(splay)，原来的右儿子边变成虚边，(x-y)的边变成实边。所以会让(x)原来的右儿子所在子树(cnt)整体+1，让(y)所在的子树(cnt)整体-1。
看到子树，应该想到dfs序。子树的(dfs)序是连续的一段。整体修改就是区间修改，询问(max)就是区间求(max)，线段树维护就行了。
(lca)随便怎么求，树剖就行，还可以顺便求出dfs序。
所以思路就是(LCT)维护颜色（一个(splay)代表一种颜色），树剖+dfs序+线段树回答询问。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,a,b) for(int i=(a),ed=(b);i<=ed;++i)
inline int read(){
register int x=0,f=1;register char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}
return f?x:-x;
}
const int N=1e5+10;
int n,m,tp[N],siz[N],son[N],dep[N],dfn[N],dfc,idf[N];
vector<int> E[N];
namespace SegmentTree{
#define ls(p) p<<1
#define rs(p) p<<1|1
int mx[N<<2],tag[N<<2];
inline void pushup(int p){mx[p]=max(mx[ls(p)],mx[rs(p)]);}
inline void pushdown(int p){
if(!tag[p])return;
tag[ls(p)]+=tag[p];tag[rs(p)]+=tag[p];
mx[ls(p)]+=tag[p];mx[rs(p)]+=tag[p];
tag[p]=0;
}
inline void build(int p,int l,int r){
if(l==r){mx[p]=dep[idf[l]];return;}
int mid=(l+r)>>1;
build(ls(p),l,mid),build(rs(p),mid+1,r);
pushup(p);
}
inline void modify(int p,int l,int r,int L,int R,int v){
if(L<=l&&r<=R){mx[p]+=v;tag[p]+=v;return;}
pushdown(p);int mid=(l+r)>>1;
if(L<=mid)modify(ls(p),l,mid,L,R,v);
if(R>mid)modify(rs(p),mid+1,r,L,R,v);
pushup(p);
}
inline int query(int p,int l,int r,int L,int R){
if(L<=l&&r<=R)return mx[p];
pushdown(p);int mid=(l+r)>>1,ans=0;
if(L<=mid)ans=max(ans,query(ls(p),l,mid,L,R));
if(R>mid)ans=max(ans,query(rs(p),mid+1,r,L,R));
pushup(p);return ans;
}
}using namespace SegmentTree;
namespace TCP{
int fa[N];
inline void dfs(int nw,int dad){
fa[nw]=dad;dep[nw]=dep[dad]+1;siz[nw]=1;
for(int to:E[nw])
if(to^dad){
dfs(to,nw);siz[nw]+=siz[to];
if(siz[to]>siz[son[nw]])son[nw]=to;
}
}
inline void dfs(int nw){
if(!tp[nw])tp[nw]=nw;
dfn[nw]=++dfc;idf[dfc]=nw;
if(son[nw]){tp[son[nw]]=tp[nw];dfs(son[nw]);}
for(int to:E[nw])
if(to^fa[nw]&&to^son[nw])dfs(to);
}
inline int lca(int x,int y){
while(tp[x]^tp[y]){
if(dep[tp[x]]<=dep[tp[y]])y=fa[tp[y]];
else x=fa[tp[x]];
}
return dep[x]>=dep[y]?y:x;
}
}using TCP::lca;
namespace LCT{
int fa[N],ch[N][2];
inline int getdir(int x){return x==ch[fa[x]][1];}
inline bool noroot(int x){return x==ch[fa[x]][0]||x==ch[fa[x]][1];}
inline void rotate(int x){
int f=fa[x],p=fa[f],k=getdir(x),s=ch[x][!k];
ch[x][!k]=f;ch[f][k]=s;if(noroot(f))ch[p][getdir(f)]=x;
fa[f]=x;fa[x]=p;if(s)fa[s]=f;
}
inline void splay(int x){
for(int f=fa[x];noroot(x);rotate(x),f=fa[x])
if(noroot(f))rotate(getdir(f)==getdir(x)?f:x);
}
inline int findroot(int x){
while(ch[x][0])x=ch[x][0];
return x;
}
inline void access(int x){
for(int y=0;x;y=x,x=fa[x]){
splay(x);
int a=findroot(ch[x][1]),b=findroot(y);
if(ch[x][1])modify(1,1,n,dfn[a],dfn[a]+siz[a]-1,1);
if(y)modify(1,1,n,dfn[b],dfn[b]+siz[b]-1,-1);
ch[x][1]=y;
}
}
}using LCT::access;
int main(){
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
n=read(),m=read();
REP(i,1,n-1){
int x=read(),y=read();
E[x].push_back(y),E[y].push_back(x);
}
dep[1]=1;TCP::dfs(1,0);TCP::dfs(1);build(1,1,n);
REP(i,1,n)LCT::fa[i]=TCP::fa[i];
REP(i,1,m){
int op=read();int x=read();
if(op==1)access(x);
else if(op==2){
int y=read(),p=lca(x,y),ans=0;
ans+=query(1,1,n,dfn[x],dfn[x]);
ans+=query(1,1,n,dfn[y],dfn[y]);
ans-=query(1,1,n,dfn[p],dfn[p])*2;
printf("%d
",ans+1);
}
else printf("%d
",query(1,1,n,dfn[x],dfn[x]+siz[x]-1));
}
return 0;
}