码风较为抽象

#include<iostream>
#include<cstring>
#include<vector>
#define endl '\n'
#define int long long
using namespace std;
const int maxn=2e5+10;
int n,m,w[maxn],col;
vector<int> g[maxn];
int fa[maxn],son[maxn],dep[maxn],sz[maxn];
int dfn[maxn],tim,pos[maxn],Top[maxn];
struct Segment_tree{
    struct node{
        int l,r,col_l,col_r,sum,tag;
    }tr[maxn<<2];
    inline void pushup(int u){
        tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum+(tr[u<<1].col_r==tr[u<<1|1].col_l);
        tr[u].col_l=tr[u<<1].col_l;
        tr[u].col_r=tr[u<<1|1].col_r;
        return;
    }
    inline void pushdown(int u){
        if(tr[u].tag==0){
            return;
        }
        int l=tr[u].l,r=tr[u].r;
        int mid=l+r>>1;
        tr[u<<1].sum=mid-l;
        tr[u<<1|1].sum=r-mid-1;
        tr[u<<1].tag=tr[u].tag;
        tr[u<<1|1].tag=tr[u].tag;
        tr[u<<1].col_l=tr[u].tag;
        tr[u<<1].col_r=tr[u].tag;
        tr[u<<1|1].col_l=tr[u].tag;
        tr[u<<1|1].col_r=tr[u].tag;
        tr[u].tag=0;
        return;
    }
    inline void build(int u,int l,int r){
        tr[u].l=l;
        tr[u].r=r;
        tr[u].tag=0;
        if(l==r){
            tr[u].sum=0;
            tr[u].col_l=pos[l];
            tr[u].col_r=pos[l];
            return;
        }
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
        return;
    }
    inline void modify(int u,int ql,int qr,int k){
        int l=tr[u].l,r=tr[u].r;
        if(ql<=l&&qr>=r){
            tr[u].col_l=k;
            tr[u].col_r=k;
            tr[u].tag=k;
            tr[u].sum=r-l;
            return;
        }
        pushdown(u);
        int mid=l+r>>1;
        if(ql<=mid){
            modify(u<<1,ql,qr,k);
        }
        if(qr>mid){
            modify(u<<1|1,ql,qr,k);
        }
        pushup(u);
        return;
    }
    inline int query(int u,int ql,int qr){
        int l=tr[u].l,r=tr[u].r;
        if(ql<=l&&qr>=r){
            return tr[u].sum;
        }
        pushdown(u);
        int mid=l+r>>1,res=0;
        if(ql<=mid){
            res+=query(u<<1,ql,qr);
        }
        if(qr>mid){
            res+=query(u<<1|1,ql,qr);
        }
        if(ql<=mid&&qr>mid&&tr[u<<1].col_r==tr[u<<1|1].col_l){
            res++;
        }
        return res;
    }
    inline int check(int u,int pos){
        int l=tr[u].l,r=tr[u].r;
        if(l==r){
            return tr[u].col_l;
        }
        int mid=l+r>>1;
        if(pos<=mid){
            return check(u<<1,pos);
        }else{
            return check(u<<1|1,pos);
        }
    }
}Tr;
inline void init(){
    for(int i=1;i<=n;i++){
        g[i].clear();
    }
    memset(w,0,sizeof(w));
    col=0;
    memset(fa,0,sizeof(fa));
    memset(son,0,sizeof(son));
    memset(dep,0,sizeof(dep));
    memset(sz,0,sizeof(sz));
    memset(dfn,0,sizeof(dfn));
    tim=0;
    memset(pos,0,sizeof(pos));
    memset(Top,0,sizeof(Top));
    return;
}
inline void dfs1(int u,int fath){
    fa[u]=fath;
    dep[u]=dep[fath]+1;
    sz[u]=1;
    int mx=-1;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(v==fath){
            continue;
        }
        dfs1(v,u);
        sz[u]+=sz[v];
        if(sz[v]>mx){
            mx=sz[v];
            son[u]=v;
        }
    }
    return;
}
inline void dfs2(int u,int tp){
    dfn[u]=++tim;
    Top[u]=tp;
    pos[tim]=w[u];
    if(son[u]==0){
        return;
    }
    dfs2(son[u],tp);
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(v==fa[u]||v==son[u]){
            continue;
        }
        dfs2(v,v);
    }
    return;
}
inline void update(int u,int v){
    col++;
    while(Top[u]!=Top[v]){
        if(dep[Top[u]]<dep[Top[v]]){
            swap(u,v);
        }
        Tr.modify(1,dfn[Top[u]],dfn[u],1);
        u=fa[Top[u]];
    }
    if(dep[u]>dep[v]){
        swap(u,v);
    }
    Tr.modify(1,dfn[u],dfn[v],col);
    return;
}
inline int ask(int u,int v){
    int res=0;
    while(Top[u]!=Top[v]){
        if(dep[Top[u]]<dep[Top[v]]){
            swap(u,v);
        }
        res+=Tr.query(1,dfn[Top[u]],dfn[u]);
        if(Tr.check(1,dfn[fa[Top[u]]])==Tr.check(1,dfn[Top[u]])){
            res++;
        }
        u=fa[Top[u]];
    }
    if(dep[u]>dep[v]){
        swap(u,v);
    }
    res+=Tr.query(1,dfn[u],dfn[v]);
    return res;
}
inline void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        w[i]=++col;
    }
    for(int i=1;i<=n-1;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(1,0);
    dfs2(1,1);
    Tr.build(1,1,n);
    while(m--){
        int opt,x,y;
        cin>>opt>>x>>y;
        if(opt==1){
            update(x,y);
        }else{
            int ans=ask(x,y);
            cout<<ans<<endl;
        }
    }
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        init();
        solve();
    }
    return 0;
}