#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int size=4e5;
template <class type>
class segment_tree
{
	private:
		template <class type_node>
		struct node{int l;int r;type_node flag;int t;};
		node<type> t[size];
		void build(int id,int l,int r)
		{
			t[id].l=l;
			t[id].r=r;
			t[id].flag=0;
			if(l!=r)
			{
				build(id*2,l,(l+r)/2);
				build(id*2+1,(l+r)/2+1,r);
			}
		}
		void change(int id,int l,int r,type x,int time_stamp)
		{
			if(t[id].l==l&&t[id].r==r)
			{
				t[id].flag=x;t[id].t=time_stamp;
				return;
			}
			int mid=(t[id].l+t[id].r)/2;
			bool b1=(t[id].l<=l&&l<=mid),b2=(mid+1<=r&&r<=t[id].r);
			if(b1&&b2)
			{
				change(id*2,l,mid,x,time_stamp);
				change(id*2+1,mid+1,r,x,time_stamp);
			}
			else if(b1&&!b2)
				change(id*2,l,r,x,time_stamp);
			else if(!b1&&b2)change(id*2+1,l,r,x,time_stamp);
		}
		template <class type3>
		struct data
		{
			int level;
			type3 value;
		};
		data<type> request(int id,int x)
		{
			data<type>tmp=data<type>{t[id].t,t[id].flag};
			if(t[id].l!=t[id].r)
			{
				data<type>next;
				if(t[id].l<=x&&x<=((t[id].l+t[id].r)/2))
				{
					next=request(id*2,x);
				}
				else if(((t[id].l+t[id].r)/2+1)<=x&&x<=t[id].r)
				{
					next=request(id*2+1,x);
				}
				if(next.level>tmp.level)
				{
					tmp=next;
				}
			}
			return tmp;
		}
		int time_stamp;
	public:
		segment_tree()
		{
			time_stamp=0;
			build(1,1,size/4);
		}
		segment_tree(int n)
		{
			time_stamp=0;
			build(1,1,n);
		}
		void change(int l,int r,type x)
		{
			time_stamp++;
			change(1,l,r,x,time_stamp);
		}
		type request(int id)
		{
			return request(1,id).value;
		}
};
segment_tree<int> t1;//维护颜色 
const int used_size=4e5;
template <class type>
class segment_tree2
{
	//需要支持区间推平，区间求和
	private:
		template <class node_type>
		struct node
		{
			int l,r;
			node_type sum,lazy;
			int ls,rs;
		};
		node<type> t[used_size];
		int cnt;
		void crate(int id)
	    {
	        if(t[id].ls==0&&t[id].rs==0&&t[id].l!=t[id].r)
	        {
	            int mid=(t[id].l+t[id].r)/2;
	            cnt++;
	            t[cnt].l=t[id].l;
	            t[cnt].r=mid;
	            t[cnt].lazy=-0x7fffffff;
	            t[cnt].sum=0;
	            t[id].ls=cnt;
	            cnt++;
	            t[cnt].l=mid+1;
	            t[cnt].r=t[id].r;
	            t[cnt].lazy=-0x7fffffff;
	            t[cnt].sum=0;
	            t[id].rs=cnt;
	        }
	    }
	    inline void update(int id)
	    {
	        crate(id);
	        if(t[id].lazy!=-0x7fffffff)
	        {
	        	t[id].sum=t[id].lazy*(t[id].r-t[id].l+1);
	        	if(t[id].l!=t[id].r)
	        	{
					t[t[id].ls].lazy=t[id].lazy;
	        		t[t[id].rs].lazy=t[id].lazy;
	        	}
				t[id].lazy=-0x7fffffff;
			}
	    }
	    void change(int id,int l,int r,type k)
		{
			update(id);
			if(t[id].l==l&&t[id].r==r)
			{
				t[id].lazy=k;
				update(id);
				return ;
			}
			int mid=(t[id].l+t[id].r)>>1;
			bool f1=(l<=mid),f2=(mid<r);
			if(f1&&f2)
			{
				change(t[id].ls,l,mid,k);
				change(t[id].rs,mid+1,r,k);
			}
			else if(f1)
				change(t[id].ls,l,r,k);
			else
				change(t[id].rs,l,r,k);
			update(t[id].ls);
			update(t[id].rs);
			t[id].sum=t[t[id].ls].sum+t[t[id].rs].sum;
		}
		type sum(int id,int l,int r)
		{
			update(id);
			if(t[id].l==l&&t[id].r==r)
				return t[id].sum;
			int mid=(t[id].l+t[id].r)>>1;
			bool f1=(l<=mid),f2=(mid<r);
			if(f1&&f2)
			{
				int a=sum(t[id].ls,l,mid);
				int b=sum(t[id].rs,mid+1,r);
				return a+b;
			}
			else if(f1)
				return sum(t[id].ls,l,r);
			else
				return sum(t[id].rs,l,r);
		}
	public:
		segment_tree2()
	    {
	    	cnt=1;
			t[1].l=1;
			t[1].r=1e5;
			t[1].lazy=-0x7fffffff;
			t[1].sum=0;
	    }
	    void change(int l,int r,type k)
	    {
	    	change(1,l,r,k);
		}
		type sum(int l,int r)
		{
			return sum(1,l,r);
		}
};
segment_tree2<int> t2;
int n,m,color;
vector<int> e[100005];
int d[100005],s[100005],f[100005];
void dfs1(int id,int last)
{
	s[id]=1;
	d[id]=d[last]+1;
	f[id]=last;
	for(int i=0;i<=e[id].size()-1;i++)
		if(e[id][i]!=last)
		{
			dfs1(e[id][i],id);
			s[id]+=s[e[id][i]];
		}
}
int p[100005],h[100005],heavy[100005],cnt;
void dfs2(int id,int last)
{
	cnt++;
	p[id]=cnt;
	if(!h[id])
		h[id]=id;
	int maxium=0,maxid=-1;
	for(int i=0;i<e[id].size();i++)
		if(e[id][i]!=last&&s[e[id][i]]>maxium)
		{
			maxium=s[e[id][i]];
			maxid=i;
		}
	if(maxid==-1)
		return ;
	heavy[id]=e[id][maxid];
	h[e[id][maxid]]=h[id];
	dfs2(e[id][maxid],id);
	for(int i=0;i<e[id].size();i++)
		if(e[id][i]!=last&&i!=maxid)
			dfs2(e[id][i],id);
}
void change(int u,int v,int c)//把从u到v的一段重链的颜色覆盖为c
{
	if(d[u]>d[v])
		swap(u,v);
	t1.change(p[u],p[v],c);
	if(u!=v)
		t2.change(p[heavy[u]],p[v],1);
	if(heavy[f[u]]==u&&t1.request(p[f[u]])==c)
		t2.change(p[u],p[u],1);
	else
		t2.change(p[u],p[u],0);
	if(heavy[v]&&t1.request(p[heavy[v]])==c)
		t2.change(p[heavy[v]],p[heavy[v]],1);
	else
		t2.change(p[heavy[v]],p[heavy[v]],0);
}
void lca1(int u,int v,int c)//染色 
{
	while(h[u]!=h[v])
		if(d[h[u]]<d[h[v]])
		{
			change(v,h[v],c);
			v=f[h[v]];
		}
		else
		{
			change(u,h[u],c);
			u=f[h[u]];
		}
	if(p[u]>p[v])
		swap(u,v);
	change(u,v,c);
}
int lca2(int u,int v)//查询
{
	int cnt_u=0,cnt_v=0,color_u=0,color_v=0;
	while(h[u]!=h[v])
		if(d[h[u]]<d[h[v]])
		{
			if(h[v]!=v)
				cnt_v+=t2.sum(p[heavy[h[v]]],p[v]);
			if(t1.request(p[v])==color_v)
				cnt_v++;
			color_v=t1.request(p[h[v]]);
			v=f[h[v]];
		}
		else
		{
			if(h[u]!=u)
				cnt_u+=t2.sum(p[heavy[h[u]]],p[u]);
			if(t1.request(p[u])==color_u)
				cnt_u++;
			color_u=t1.request(p[h[u]]);
			u=f[h[u]];
		}
	if(u!=v)
	{
		if(p[u]>p[v])
		{
			swap(u,v);
			swap(cnt_u,cnt_v);
			swap(color_u,color_v);
		}
		cnt_u+=t2.sum(p[heavy[u]],p[v]);
	}
	if(color_u==t1.request(p[u]))
		cnt_u++;
	if(color_v==t1.request(p[v]))
		cnt_v++;
	return cnt_v+cnt_u;
}
void init()
{
	n=m=color=cnt=0;
	for(int i=1;i<=1e5;i++)
		e[i].clear();
	for(int i=1;i<=1e5;i++)
		d[i]=s[i]=f[i]=p[i]=h[i]=heavy[i]=0;
	t1.change(1,1e5,0);
	t2.change(1,1e5,0);
}
int mian()
{
	init();
	cin>>n>>m;
	color=n;
	for(int i=1;i<=n;i++)
		t1.change(i,i,i);
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs1(1,0);
	dfs2(1,0);
	for(int i=1;i<=m;i++)
	{
		int op,u,v;
		cin>>op>>u>>v;
		if(op==1)
		{
			color++;
			lca1(u,v,color);
		}
		else if(op==2)
			cout<<lca2(u,v)<<"\n";
	}
	return 0;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	for(int i=1;i<=t;i++)
		mian();
	return 0;
}

评测记录

被卡常了4个点，不知道怎么卡常了