记录编号	586363	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2021]轻重边	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	6.371 s
提交时间	2024-01-15 20:37:09	内存使用	56.39 MiB

#include <bits/stdc++.h>
using namespace std;
#define me(x,z) memset(x,z,sizeof(x))
const int N = 1e5+10,M = 2e5+10;
int T,n,m;
struct made{
    int ver,nx;
}e[M<<1];
int hd[N],tot,cnt;
int size[N],son[N],dep[N],fa[N];
int dfn[N],rnk[N],top[N];
struct Tree{
    int l,r,ls,rs,sum,la;
    #define l(x) t[x].l 
    #define r(x) t[x].r 
    #define ls(x) t[x].ls
    #define rs(x) t[x].rs 
    #define sum(x) t[x].sum
    #define la(x) t[x].la 
}t[N<<4];
Tree operator + (Tree x,Tree y){
    Tree s;
    s.l = x.l,s.r = y.r;
    s.ls = x.ls,s.rs = y.rs;
    s.sum = x.sum + y.sum;
    s.la = 0;//未初始化为0调了30min 
    if(x.rs == y.ls)s.sum++;
    return s;
}
void update(int x,int z){
    la(x) = ls(x) = rs(x) = z;
    sum(x) = r(x) - l(x);
}
void pushdown(int x){
    if(!la(x))return;
    update(x<<1,la(x));
    update(x<<1|1,la(x));
    la(x) = 0;
}
void build(int x,int l,int r){
    l(x) = l,r(x) = r,la(x) = 0,sum(x) = 0;
    if(l == r){
        ls(x) = rs(x) = l;
        return;
    }
    int mid = l + r >> 1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    t[x] = t[x<<1] + t[x<<1|1];
}
void modify(int x,int l,int r,int z){
    if(l <= l(x) && r(x) <= r){
        update(x,z);
        return;
    }
    pushdown(x);
    int mid = l(x) + r(x) >> 1;
    if(l <= mid)modify(x<<1,l,r,z);
    if(r > mid)modify(x<<1|1,l,r,z);
    t[x] = t[x<<1] + t[x<<1|1]; 
}
Tree ask(int x,int l,int r){
    if(l <= l(x) && r(x) <= r)return t[x];
    pushdown(x);
    int mid = l(x) + r(x) >> 1;
    if(r <= mid)return ask(x<<1,l,r);
    else if(l > mid)return ask(x<<1|1,l,r);
    else return ask(x<<1,l,r) + ask(x<<1|1,l,r);
}
//--------------------------
void add(int x,int y){
    tot++;
    e[tot].nx = hd[x],e[tot].ver = y,hd[x] = tot;
}
void dfs1(int x){
    size[x] = 1;
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(dep[y])continue;
        dep[y] = dep[x] + 1;
        fa[y] = x;
        dfs1(y);
        size[x] += size[y];
        if(!son[x] || size[y] > size[son[x]])son[x] = y;
    }
}
void dfs2(int x,int t){
    dfn[x] = ++cnt,top[x] = t;
    rnk[cnt] = x;
    if(!son[x])return;
    dfs2(son[x],t);
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(y != fa[x] && y != son[x])dfs2(y,y);
    }
}
void calmodify(int x,int y,int z){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])swap(x,y);
        modify(1,dfn[top[x]],dfn[x],z);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y])swap(x,y);
    modify(1,dfn[x],dfn[y],z);
}
int calask(int x,int y){
    Tree L,R;
    L.ls = L.rs = L.sum = L.l = L.r = 0;R = L; 
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])swap(x,y),swap(L,R);
        if(L.ls == 0)L = ask(1,dfn[top[x]],dfn[x]);
        else L = ask(1,dfn[top[x]],dfn[x]) + L;
        x = fa[top[x]];
    }
    if(dep[x] > dep[y])swap(x,y),swap(L,R);
    if(R.ls == 0)R = ask(1,dfn[x],dfn[y]);
    else R = ask(1,dfn[x],dfn[y]) + R;
    swap(L.ls,L.rs);
    return (L + R).sum;
}
void work(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i < n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    dep[1] = 1;
    dfs1(1),dfs2(1,1);
    build(1,1,n);
    for(int i = 1;i <= m;i++){
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        switch(op){
            case 1:calmodify(x,y,++cnt);break;
            case 2:printf("%d\n",calask(x,y));break;
        }
    }
    return;
}
void first(){
    tot = cnt = 0;
    me(size,0);
    memset(hd,0,sizeof(hd));
    memset(size,0,sizeof(size));
    memset(e,0,sizeof(e));
    memset(son,0,sizeof(son));
    memset(t,0,sizeof(t));
    memset(dep,0,sizeof(dep));
}
int main(){
    freopen("noi2021_edge.in","r",stdin);
    freopen("noi2021_edge.out","w",stdout);
    scanf("%d",&T);
    while(T--){
        first();
        work();
    }
    
    return 0;
    
}