我一开始以为TLE是因为数剖常数太大了，没想到深层递归爆缓存了求调（orz）

#include <bits/stdc++.h>
using namespace std;
struct node {
	long long l, r;
	long long cnt;
	long long tag; 
};
node tree[5000001];
void make(long long i, long long l, long long r, long long x, long long y, long long k) {
	if(tree[i].tag&&l!=r) {
		make(i*2,l,(l+r)>>1,l,(l+r)>>1,tree[i].tag);
		make(i*2+1,((l+r)>>1)+1,r,((l+r)>>1)+1,r,tree[i].tag);
		tree[i].cnt=r-l;
		tree[i].tag=0;
	}
	if (l == x && r == y) {
		tree[i].l = k;
		tree[i].r = k;
		tree[i].cnt = r - l;
		tree[i].tag = k;
		return;
	}
	long long mid = (l + r) >> 1;
	if (mid >= y) {
		make(i * 2, l, mid, x, y, k);
		if (y == mid)
			tree[i].l = k;
		tree[i].cnt = tree[i * 2].cnt + tree[i * 2 + 1].cnt+(tree[i].l==tree[i].r&&tree[i].l);
		
	} else {
		if (mid + 1 <= x) {
			make(i * 2 + 1, mid+1, r, x, y, k);
			if (x == mid + 1)
				tree[i].r = k;
			tree[i].cnt = tree[i * 2].cnt + tree[i * 2 + 1].cnt+(tree[i].l==tree[i].r&&tree[i].l);
		} else {
			make(i * 2, l, mid, x, mid, k);
			make(i * 2 + 1, mid + 1, r, mid + 1, y, k);
			tree[i].l = k;
			tree[i].r = k;
			tree[i].cnt = tree[i * 2].cnt + tree[i * 2 + 1].cnt + 1;
		}
	}
}
long long anwser(long long i, long long l, long long r, long long x, long long y) {
	if(tree[i].tag&&l!=r) {
		make(i*2,l,(l+r)>>1,l,(l+r)>>1,tree[i].tag);
		make(i*2+1,((l+r)>>1)+1,r,((l+r)>>1)+1,r,tree[i].tag);
		tree[i].l = tree[i].tag;
		tree[i].r = tree[i].tag;
		tree[i].cnt = tree[i * 2].cnt + tree[i * 2 + 1].cnt + 1;
		tree[i].tag=0;
	}
	if (l == x && r == y) 
		return tree[i].cnt;
	long long mid = (l + r) >> 1;
	if (mid >= y) {
		return anwser(i * 2, l, mid, x, y);
	} else {
		if (mid + 1 <= x) {
			return anwser(i * 2 + 1, mid+1, r, x, y);
		} else {
			return anwser(i * 2, l, mid, x, mid) + anwser(i * 2 + 1, mid + 1, r, mid + 1, y) + (tree[i].l == tree[i].r&&tree[i].l);
		}
	}
}
long long find(long long i,long long l,long long r,long long x) {
	if(tree[i].tag&&l!=r) {
		tree[i].cnt=r-l;
		make(i*2,l,(l+r)>>1,l,(l+r)>>1,tree[i].tag);
		make(i*2+1,((l+r)>>1)+1,r,((l+r)>>1)+1,r,tree[i].tag);
		tree[i].l = tree[i].tag;
		tree[i].r = tree[i].tag;
		tree[i].cnt = tree[i * 2].cnt + tree[i * 2 + 1].cnt + 1;
		long long temp=tree[i].tag;
		tree[i].tag=0;
		return temp;
	}
	if (l == r)
		return tree[i].tag;
	long long mid = (l + r) >> 1;
	if (mid >= x) {
		return find(i * 2, l, mid,x);
	} else {
		return find(i * 2 + 1, mid+1, r, x);
	}
} 
vector<long long>edge[100001];
long long cnt, ids[100001], top[100001], dep[100001], fa[100001], sum[100001], son[100001];
inline void dfs1(long long o, long long fas, long long dp) {
	dep[o] = dp;
	fa[o] = fas;
	sum[o] = 1;
	int bison = -100000000;
	for (int i = 0; i < edge[o].size(); i++) {
		long long y = edge[o][i];
		if (y == fas)
			continue;
		dfs1(y, o, dp + 1);
		sum[o] += sum[y];
		if (sum[y] > bison)
			son[o] = y, bison = sum[y];
	}
}
void dfs2(long long o, long long fas) {
	ids[o] = ++cnt;
	top[o] = fas;
	if (!son[o])
		return;
	dfs2(son[o], fas);
	for (int i = 0; i < edge[o].size(); i++) {
		long long t = edge[o][i];
		if (t == fa[o] || t == son[o])
			continue;
		dfs2(t, t);
	}
}
long long n, m;
void do1(long long a, long long b, long long c) {
	while (top[a] != top[b]) {
		if (dep[top[a]] < dep[top[b]])
			swap(a, b);
		make(1,1,n, ids[top[a]], ids[a], c);
		a = fa[top[a]];
	}
	if (ids[a] > ids[b])
		swap(a, b);
	make(1, 1,n,ids[a], ids[b], c);
}
long long do2(long long a, long long b) {
	long long ans = 0,jjja=0,jjjb=0;
	while (top[a] != top[b]) {
		if (dep[top[a]] < dep[top[b]]) {
			ans+=anwser(1,1,n,ids[top[b]],ids[b]);
			long long temp=find(1,1,n,ids[top[b]]);
			if(temp==find(1,1,n,ids[fa[top[b]]])&&temp)	
				ans++;
			b=fa[top[b]];
		} else {
			ans += anwser(1, 1, n, ids[top[a]], ids[a]);
			long long temp=find(1,1,n,ids[top[a]]);
			if(temp==find(1,1,n,ids[fa[top[a]]])&&temp)
				ans++;
			a = fa[top[a]];
		}
	}
	if (dep[a] > dep[b])
		swap(a, b);
	return ans + anwser(1, 1, n, ids[a], ids[b]);
}
int main() {
 	freopen("P7735_7.in","r",stdin);
//	freopen("edge2.out","w",stdout);
	long long s;
	cin >> s;
	for (int fds = 1; fds <= s; fds++) {
		cin >> n >> m;
		for (int j = 1; j < n; j++) {
			long long ccf,fuck;
			scanf("%lld%lld",&ccf,&fuck);
			edge[fuck].push_back(ccf);
			edge[ccf].push_back(fuck);
		}
		dfs1(1, 1, 1);
		dfs2(1, 1);
		for (int i = 1; i <= m; i++) {
			long long op, a, b;
			scanf("%lld%lld%lld",&op,&a,&b);
			if (op == 1)
				do1(a, b,i);
			else
				printf("%lld\n",do2(a,b));
		}
		for(int i=1;i<=100000;i++)
			edge[i].clear(),cnt=ids[i]=top[i]=dep[i]=fa[i]=sum[i]=son[i]=0;
		for(int i=1;i<=400000;i++)
			tree[i].cnt=tree[i].l=tree[i].r=tree[i].tag=0;
		cnt=0;
	}
	return 0;
}