更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19638717

大意

给定两个点 $a$ 和 $b$，首先对于 $a$ 到 $b$ 路径上的所有点 $x$（包含 $a$ 和 $b$），你要将与 $x$ 相连的所有边变为轻边。然后再将 $a$ 到 $b$ 路径上包含的所有边变为重边。

给定两个点 $a$ 和 $b$，你需要计算当前 $a$ 到 $b$ 的路径上一共包含多少条重边。

思路

我们考虑一个小巧思。

我们将问题可以转化为将 $a \to b$ 这条路径的点染上独一无二的颜色，最终求 $a \to b$ 路径上的重边即为两端颜色相同的边的数量。

因为每次我们选的颜色都不一样，这样操作一定能够让我们通过只记录端点的颜色去统计这个值，我们通过直接维护区间的左右的端点的颜色和相邻重色的个数，我们如果区间的端点颜色重合就可以将这个答案继续累加。这个就是处理本题线段树的方式。

但是对于这个题目是在树上的操作，那就没什么说的了，直接树剖维护即可。但是如果你像我一样闲着没事的话可以用 LCT 维护，原因是这个更改 $a \to b$ 路径的过程可以用 LCT 的 split 操作非常简便的完成。至于 LCT 里面维护的内容，和线段树几乎一样，剩下就没什么了。

代码

#include<iostream>
#include<algorithm>
using namespace std;

#define lc(x) t[x].ch[0]
#define rc(x) t[x].ch[1]
#define fa(x) t[x].fa
const int MAXN = 1e5 + 5;

struct node{
    int ch[2], fa;
    int col, tag;
    int lc, rc;
    int cnt; 
    int sz;
    bool rev;
    node(){
        ch[1] = ch[0] = fa = 0;
        col = tag = lc = rc = cnt = sz = 0;
        rev = false;
    }
}t[MAXN];

bool isroot(int x){
    return (lc(fa(x)) != x) && (rc(fa(x)) != x);
}

void pushup(int x) {
    t[x].sz = t[lc(x)].sz + t[rc(x)].sz + 1;
    t[x].cnt = t[lc(x)].cnt + t[rc(x)].cnt;
    
    t[x].lc = lc(x) ? t[lc(x)].lc : t[x].col;
    t[x].rc = rc(x) ? t[rc(x)].rc : t[x].col;
    
    if(lc(x) && t[lc(x)].rc == t[x].col) t[x].cnt ++;
    if(rc(x) && t[rc(x)].lc == t[x].col) t[x].cnt ++;
}

void update_rev(int x){
    if(!x) return;
    swap(lc(x), rc(x));
    swap(t[x].lc, t[x].rc);
    t[x].rev ^= 1;
}

void apply_col(int x, int c){
    if(!x) return;
    t[x].col = t[x].lc = t[x].rc = t[x].tag = c;
    t[x].cnt = t[x].sz - 1;
}

void pushdown(int x){
    if(t[x].rev){
        update_rev(lc(x));
        update_rev(rc(x));
        t[x].rev = 0;
    }
    if(t[x].tag){
        apply_col(lc(x), t[x].tag);
        apply_col(rc(x), t[x].tag);
        t[x].tag = 0;
    }
}

void rotate(int x){
    int y = fa(x), z = fa(y);
    int k = (rc(y) == x);
    if(!isroot(y)) t[z].ch[rc(z) == y] = x;
    fa(x) = z;
    t[y].ch[k] = t[x].ch[k ^ 1];
    if (t[x].ch[k ^ 1]) fa(t[x].ch[k ^ 1]) = y;
    t[x].ch[k ^ 1] = y;
    fa(y) = x;
    pushup(y);
    pushup(x);
}

void pushshell(int x){
    if(!isroot(x)) pushshell(fa(x));
    pushdown(x);
}

void splay(int x){
    pushshell(x);
    while(!isroot(x)){
        int y = fa(x), z = fa(y);
        if(!isroot(y)) (rc(z) == y) ^ (rc(y) == x) ? rotate(x) : rotate(y);
        rotate(x);
    }
}

void access(int x){
    for(int y = 0;x;y = x, x = fa(x)){
        splay(x);
        rc(x) = y;
        pushup(x);
    }
}

void makeroot(int x){
    access(x);
    splay(x);
    update_rev(x);
}

void split(int x, int y){
    makeroot(x);
    access(y);
    splay(y);
}

void modify(int u, int v, int c){
    split(u, v);
    apply_col(v, c);
}

void solve(){
    int n, m; cin >> n >> m;
    for(int i = 1;i <= n;i ++){
        t[i] = node();
        t[i].col = t[i].lc = t[i].rc = -i;
        t[i].sz = 1;
    }
    for(int i = 1;i < n;i ++){
        int u, v; cin >> u >> v;
        makeroot(u); fa(u) = v;
    }
    int cur_col = 0;
    while(m --){
        int op, u, v;
        cin >> op >> u >> v;
        if(op == 1){
            modify(u, v, ++ cur_col);
            split(u, v);
            apply_col(v, ++ cur_col);
        }
		else{
            split(u, v);
            cout << t[v].cnt << "\n";
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T; cin >> T;
    while(T --) solve();
    return 0;
}