#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define c(a) memset(a,0,sizeof(a))
int n,m;
int head[100010];
int to[200010];
int nxt[200010];
int tot = 0;
inline void add(int x,int y)
{
	to[++tot] = y;
	nxt[tot] = head[x];
	head[x] = tot;
	return;
}
int idx = 0;
int dfn[100010];
int fa[100010];
int siz[100010];
int son[100010];
int top[100010];
int dep[100010];

int top_num[100010];
int head1[100010];
int nxt1[100010];
int to1[100010];
int tot1 = 0;
int cnt1 = 1;
inline void add1(int x,int y)
{
	to1[++tot1] = y;
	nxt1[tot1] = head1[x];
	head1[x] = tot1;
	return;
}
int num[100010];
inline void dfs1(int x,int f)
{
	dep[x] = dep[f] + 1;
	fa[x] = f;
	siz[x] = 1;
	for(int i = head[x]; i; i = nxt[i])
	{
		int v = to[i];
		if(v == f) continue;
		dfs1(v,x);
		siz[x] += siz[v];
		if(siz[v] > siz[son[x]]) son[x] = v;
	}
	return;
}
inline void dfs2(int x,int tp)
{
	top_num[cnt1] = tp;
	num[x] = cnt1;
	dfn[x] = ++idx;
	top[x] = tp;
	if(son[x]) dfs2(son[x],tp);
	for(int i = head[x]; i; i = nxt[i])
	{
		int v = to[i];
		if(v == fa[x] || v == son[x]) continue;
		cnt1++;
		add1(num[x],cnt1);
		dfs2(v,v);
	}
}
struct node
{
	int sum;
	int lazy;
	int len;
} tree[400010];
inline void build(int x,int l,int r)
{
	tree[x].len = r - l + 1;
	if(l == r) return;
	int mid = (l + r) / 2;
	build(x * 2,l,mid);
	build(x * 2 + 1,mid + 1,r);
	return;
}
inline void pushup(int x)
{
	tree[x].sum = tree[x * 2].sum + tree[x * 2 + 1].sum;
	return;
}
inline void pushdown(int x)
{
	if(tree[x].lazy == 0) return;
	if(tree[x].lazy == -1)
	{
		tree[x * 2].sum = 0;
		tree[x * 2 + 1].sum = 0;
		tree[x * 2].lazy = -1;
		tree[x * 2 + 1].lazy = -1;
	}
	else
	{
		tree[x * 2].sum = tree[x * 2].len;
		tree[x * 2 + 1].sum = tree[x * 2 + 1].len;
		tree[x * 2].lazy = 1;
		tree[x * 2 + 1].lazy = 1;
	}
	tree[x].lazy = 0;
	return;
}
inline void update(int x,int l,int r,int L,int R,int k)
{
//	if(k == 0 && tree[x].sum == 0) return;
	if(L <= l && r <= R)
	{
		tree[x].sum = k * (r - l + 1);
		tree[x].lazy = k ? 1 : -1;
		return;
	}
	pushdown(x);
	int mid = (l + r) / 2;
	if(L <= mid) update(x * 2,l,mid,L,R,k);
	if(R > mid) update(x * 2 + 1,mid + 1,r,L,R,k);
	pushup(x);
	return;
}
inline int query(int x,int l,int r,int L,int R)
{
	if(L <= l && r <= R)
	{
		return tree[x].sum;
	}
	pushdown(x);
	int mid = (l + r) / 2;
	int res = 0;
	if(L <= mid) res += query(x * 2,l,mid,L,R);
	if(R > mid) res += query(x * 2 + 1,mid + 1,r,L,R);
	return res;
}
inline void clear()
{
	c(head);
	c(nxt);
	c(to);
	c(head1);
	c(nxt1);
	c(to1);
	tot = tot1 = idx = 0;
	cnt1 = 1;
	c(dfn);
	c(top);
	c(top_num);
	c(num);
	c(fa);
	c(siz);
	c(son);
	c(dep);
	c(tree);
	return;
}
int t;

int main()
{
	ios::sync_with_stdio(false);
	cin >> t;

	while(t--)
	{
		cin >> n >> m;
		build(1,1,n);
		for(int i = 1,x,y; i < n; ++i)
		{
			cin >> x >> y;
			add(x,y);
			add(y,x);
		}
		dfs1(1,1);
		dfs2(1,1);
//		cout << endl;
//		for(int i = 1;i <= 4;++i) cout << top_num[i] << " ";
//
//		cout << endl << endl;
//		for(int i = 1;i <= n;++i) cout << num[i] << " ";
//
//		cout << endl << endl;
//		for(int i = 1;i <= n;++i) cout << dfn[i] << " ";
//
//		cout << endl << endl;
		while(m--)
		{
			int op;
			cin >> op;
			if(op == 1)
			{
				int x,y;
				cin >> x >> y;
				int xx = x,yy = y;
				for(int i = head[xx]; i; i = nxt[i])
				{
					int v = to[i];
					if(v == fa[xx]) continue;
					update(1,1,n,dfn[v],dfn[v],0);
				}
				update(1,1,n,dfn[xx],dfn[xx],0);
				for(int i = head[yy]; i; i = nxt[i])
				{
					int v = to[i];
					if(v == fa[yy]) continue;
					update(1,1,n,dfn[v],dfn[v],0);
				}
				update(1,1,n,dfn[yy],dfn[yy],0);
				while(top[xx] != top[yy])
				{
					if(dep[top[xx]] < dep[top[yy]]) swap(xx,yy);
					int pos = num[xx];
					for(int i = head1[pos]; i; i = nxt1[i])
					{
						int v = to1[i];
						int v_top = top_num[v];
						update(1,1,n,dfn[v_top],dfn[v_top],0);
					}
					if(son[xx]) update(1,1,n,dfn[son[xx]],dfn[son[xx]],0);
					if(son[yy]) update(1,1,n,dfn[son[yy]],dfn[son[yy]],0);
					xx = fa[top[xx]];
				}
				if(dep[xx] < dep[yy]) swap(xx,yy);
				int pos = num[xx];
				for(int i = head1[pos]; i; i = nxt1[i])
				{
					int v = to1[i];
					int v_top = top_num[v];
					if(dfn[fa[v_top]] < dfn[yy] || dfn[fa[v_top]] > dfn[xx]) continue;
					update(1,1,n,dfn[v_top],dfn[v_top],0);
				}
				if(son[xx]) update(1,1,n,dfn[son[xx]],dfn[son[xx]],0);
				if(yy != 1) update(1,1,n,dfn[yy],dfn[yy],0);
				while(top[x] != top[y])
				{
					if(dep[top[x]] < dep[top[y]]) swap(x,y);
					update(1,1,n,dfn[top[x]],dfn[x],1);
					x = fa[top[x]];
				}
				if(x != y)
				{
					if(dep[x] < dep[y]) swap(x,y);
					update(1,1,n,dfn[y] + 1,dfn[x],1);
				}
//				cout << endl;
//				for(int i = 1;i <= n;++i) cout << query(1,1,n,dfn[i],dfn[i]) << " ";
//				cout << endl << endl;
			}
			if(op == 2)
			{
				int x,y;
				cin >> x >> y;
				int res = 0;
				while(top[x] != top[y])
				{
					if(dep[top[x]] < dep[top[y]]) swap(x,y);
					res += query(1,1,n,dfn[top[x]],dfn[x]);
					x = fa[top[x]];
				}
				if(x != y)
				{
					if(dep[x] < dep[y]) swap(x,y);
					res += query(1,1,n,dfn[y] + 1,dfn[x]);
				}
				cout << res << endl;
			}
		}
		clear();
	}

	return 0;
}

我的树剖本身写的没问题， 只是在LCA部分时间复杂度好像伪了 我的思路是记录下不同链间的从属关系，

对路径上相邻的和端点处相邻的进行修改 链的特殊性质那里我WA了 后面TLE