不得不说今年难度比去年小了很多。不过不管哪一年白都是时代的眼泪呢。

这题上来 0s 想到树剖，然后考虑维护。想了 5min 想到了 ix35 鸽鸽的写法，然后觉着不好写继续想，推了 1h 以后推出了这个写法（我伞兵， ix35 鸽鸽才是 yyds ！！！！ 11111 ）。

先把拿到的树顺手剖分，然后考虑1操作。我一开始的想法是边权下放到点权以后直接维护最后一次操作的时间戳 last_{i}lasti​ ，然而这种做法不能很好解决轻儿子父亲被修改后的状态。然后想到 不下放，直接修点权，修改操作时直接把路径上的所有点打上时间戳。询问时，重链暴力跳，把路径上相邻两点时间戳相同的个数统计一下，每次跳到链头的时候特判链头和它父亲节点的时间戳

这种做法，用于维护树剖的线段树需要支持：区间拍平操作，区间相邻两数相等的个数统计，单点时间戳查询。每个节点维护的信息有：区间左端点的时间戳，区间右端点的时间戳，以及区间相邻两数相等的个数统计。

至于线段树实现细节可以看代码。

注意：一开始的时间戳都是0，所以需要特判左区间的右端点和右区间的左端点时间戳是否都为0，如果是则区间答案不能加一。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define _for(i,a,b) for(register int (i)=(a);(i)<=(b);(i)++)
#define For(i,a,b) for(register int (i)=(a);(i)>=(b);(i)--)
#define INF 0x7fffffff
#define il inline
#define rg register
const int N=1e5+5;
int n,m;
class Node{
    public:
        int l,r;
        int cnt,dl,dr;
        int a;
        #define l(o) t[o].l
        #define r(o) t[o].r
        #define len(o) (t[o].r-t[o].l+1)
        #define cnt(o) t[o].cnt
        #define dl(o) t[o].dl
        #define dr(o) t[o].dr
        #define a(o) t[o].a
}t[N<<2];
il void spread(int o){//延迟标记下传
    if(!a(o)) return ;
    dl(o<<1)=dr(o<<1)=dl(o<<1|1)=dr(o<<1|1)=a(o);
    cnt(o<<1)=len(o<<1)-1, cnt(o<<1|1)=len(o<<1|1)-1;
    a(o<<1)=a(o<<1|1)=a(o);
    a(o)=0;
}
il int get(int o,int x){//单点时间戳查询
    if(l(o)==r(o)) return dl(o);
    spread(o);
    int mid(l(o)+r(o)>>1);
    if(x<=mid) return get(o<<1,x);
    return get(o<<1|1,x);
}
il void init(int o){//更新当前点信息
    dl(o)=dl(o<<1),dr(o)=dr(o<<1|1);
    cnt(o)=cnt(o<<1)+cnt(o<<1|1);
    if(dr(o<<1) and dr(o<<1)==dl(o<<1|1)) ++cnt(o);//注意，如果左区间右端点和右区间左端点时间戳相同且皆不为0，答案要加一
}
il void build(int o,int l,int r){//建树
    l(o)=l, r(o)=r, a(o)=dl(o)=dr(o)=cnt(o)=0;
    if(l==r) return ;
    int mid(l+r>>1);
    build(o<<1,l,mid), build(o<<1|1,mid+1,r);
}
il void Recover(int o,int l,int r,int v){//区间推平操作
    if(l<=l(o) and r(o)<=r) return cnt(o)=len(o)-1, dl(o)=dr(o)=a(o)=v, void();
    spread(o);
    int mid(l(o)+r(o)>>1);
    if(l<=mid) Recover(o<<1,l,r,v);
    if(r>mid) Recover(o<<1|1,l,r,v);
    init(o);
}
il int ask(int o,int l,int r){//区间查询操作
    if(l<=l(o) and r(o)<=r) return cnt(o);
    spread(o);
    int mid(l(o)+r(o)>>1);
    int ans(0);
    if(l<=mid) ans+=ask(o<<1,l,r);
    if(r>mid) ans+=ask(o<<1|1,l,r);
    if(l<=mid and r>mid) ans+=(dr(o<<1) and dr(o<<1)==dl(o<<1|1));//注意这里也要考虑两者时间戳皆为0的情况
    return ans;
}
//基础边表
int tot,head[N];
class Edge{
    public:
        int to,next;
}e[N<<1];
il void add(int u,int v){ e[++tot].to=v, e[tot].next=head[u], head[u]=tot; }
//树剖裸板子
int cnt,id[N],top[N],son[N],fa[N],siz[N],dep[N];
il void dfs1(int p,int q){
    fa[p]=q, dep[p]=dep[q]+1, siz[p]=1;
    int owo(-1);
    for(int i=head[p];i;i=e[i].next){
        int o=e[i].to;
        if(o==q) continue;
        dfs1(o,p);
        siz[p]+=siz[o];
        if(siz[o]>owo){
            owo=siz[o];
            son[p]=o;
        }
    }
}
il void dfs2(int p,int q){
    top[p]=q, id[p]=++cnt;
    if(!son[p]) return ;
    dfs2(son[p],q);
    for(int i=head[p];i;i=e[i].next){
        int o=e[i].to;
        if(o==fa[p] or o==son[p]) continue;
        dfs2(o,o);
    }
}
il void addPath(int p,int q,int v){//修改路径上所有点的时间戳
    while(top[p]!=top[q]){
        if(dep[top[p]]<dep[top[q]]) swap(p,q);
        Recover(1,id[top[p]],id[p],v);
        p=fa[top[p]];
    }
    if(dep[p]>dep[q]) swap(p,q);
    Recover(1,id[p],id[q],v);
}
il int askPath(int p,int q){
    int ans(0);
    while(top[p]!=top[q]){
        if(dep[top[p]]<dep[top[q]]) swap(p,q);
        ans+=ask(1,id[top[p]],id[p]);
        if(get(1,id[top[p]])==get(1,id[fa[top[p]]]) and get(1,id[top[p]])) ++ans;//这里要特判链头及其父节点的时间戳
        p=fa[top[p]];
    }
    if(dep[p]>dep[q]) swap(p,q);
    return ans+=ask(1,id[p],id[q]);
}
int T,tots,root;
il void solve(){//多测清空
    tot=cnt=tots=0;
    memset(head,0,sizeof(head));
    memset(id,0,sizeof(id));
    memset(dep,0,sizeof(dep));
    memset(fa,0,sizeof(fa));
    memset(son,0,sizeof(son));
    memset(siz,0,sizeof(siz));
    memset(top,0,sizeof(top));
    build(1,1,n);
    root=1LL*rand()*rand()%n+1;//这里采用随机根的写法。
}
int main(){
    srand(time(NULL));
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        solve();
        _for(i,1,n-1){
            int u,v; scanf("%d%d",&u,&v);
            add(u,v), add(v,u);
        }
        dfs1(root,0);
        dfs2(root,root);
        _for(i,1,m){
            int op,u,v; scanf("%d%d%d",&op,&u,&v);
            if(op==1) addPath(u,v,++tots);//每次时间戳+1
            else printf("%d\n",askPath(u,v));
        }
    }
    return 0;
}