求条

#include<bits/stdc++.h>
#define mid (l+r)/2

using namespace std;

struct node{
	int sum,lc,rc;	
};

const int N=1e5+5;
int T;
int n,m;
vector<int> e[N];
int fa[N],dep[N]={0},son[N],siz[N];
int top[N],dfn[N]; 
node sum[N<<2]={0};
int tag[N<<2]={0};
int tot=0;

void DFS1(int pre,int now){
	dep[now]=dep[pre]+1;
	fa[now]=pre;
	int maxson=0,maxsiz=0;
	for(int i=0;i<e[now].size();i++){
		int v=e[now][i];
		if(v==pre){
			continue;
		}
		DFS1(now,v);
		siz[now]+=siz[v];
		if(siz[v]>maxsiz){
			maxson=v;
			maxsiz=siz[v];
		}
	}
	son[now]=maxson;
}

void DFS2(int now,int t){
	dfn[now]=++tot;
	top[now]=t;
	if(son[now]){
		DFS2(son[now],t);
	}
	for(int i=0;i<e[now].size();i++){
		int v=e[now][i];
		if(v!=son[now]&&v!=fa[now]){
			DFS2(v,v);
		}
	}
}

void pushup(int x){
	sum[x].sum=sum[x<<1].sum+sum[x<<1|1].sum;
	sum[x].lc=sum[x<<1].lc;
	sum[x].rc=sum[x<<1|1].rc;
}

void pushdown(int x,int l,int r){
	if(tag[x]>0){
		sum[x<<1].sum=(mid-l+1)-1;
		sum[x<<1].lc=tag[x];
		sum[x<<1].rc=tag[x];
		tag[x<<1]=tag[x];
		
		sum[x<<1|1].sum=(r-mid)-1;
		sum[x<<1|1].lc=tag[x];
		sum[x<<1|1].rc=tag[x];
		tag[x<<1|1]=tag[x];
	}	
	tag[x]=0;
}

void build(int x,int l,int r,int col){
	if(l==r){
		sum[x].sum=0;
		sum[x].lc=col;
		sum[x].rc=col;
		return ;
	}
	build(x<<1,l,mid,-col<<1);
	build(x<<1|1,mid+1,r,-col<<1|1);
	pushup(x);
}

void update(int x,int l,int r,int u,int v,int col){
	if(l>v||r<u){
		return ;
	}
	if(u<=l&&r<=v){ 
		sum[x].sum=(r-l+1)-1;
		sum[x].lc=col;
		sum[x].rc=col;
		tag[x]=col;
		return ;
	}
	pushdown(x,l,r);
	update(x<<1,l,mid,u,v,col);
	update(x<<1|1,mid+1,r,u,v,col);
	pushup(x);
	if(sum[x<<1].rc==sum[x<<1|1].lc){
		sum[x].sum++;
	}
	return ;
}

node query(int x,int l,int r,int u,int v){
	if(u<=l&&r<=v){
		return (node){sum[x].sum,sum[x].lc,sum[x].rc};
	}
	pushdown(x,l,r);
	if(v<=mid){
		node lt=query(x<<1,l,mid,u,v);
		return lt;
	}else if(u>mid){
		node rt=query(x<<1|1,mid+1,r,u,v);
		return rt;
	}else{
		node lt=query(x<<1,l,mid,u,v);
		node rt=query(x<<1|1,mid+1,r,u,v);
		node nt=(node){lt.sum+rt.sum,lt.lc,rt.rc};
		if(lt.rc==rt.lc){
			nt.sum++; 
		}
		return nt;
	}
}

int query_color(int x,int l,int r,int u){
	if(l==r){
		return sum[x].lc;
	} 
	pushdown(x,l,r);
	if(u<=mid){
		return query_color(x<<1,l,mid,u);
	}else{
		return query_color(x<<1|1,mid+1,r,u);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
		tot=0;
		for(int i=1;i<=n;i++){
			e[i].clear();
		}
		for(int i=1;i<=n*4;i++){
			tag[i]=-i;
		}
		build(1,1,n,1);
		for(int i=1;i<n;i++){
			int u,v;
			cin>>u>>v;
			e[u].push_back(v);
			e[v].push_back(u);
		}
		for(int i=1;i<=n;i++){
			siz[i]=1;
		}
		dep[0]=0;
		DFS1(0,1);
		DFS2(1,1);
		int t=0;
		for(int i=1;i<=m;i++){
			int op,a,b;
			cin>>op>>a>>b;
			if(op==1){
				++t;
				while(top[a]!=top[b]){
					if(dep[top[a]]>dep[top[b]]){
						update(1,1,n,dfn[top[a]],dfn[a],t);
						a=top[a];
						if(fa[a]!=0){
							a=fa[a];
						}
						//update(1,1,n,dfn[a],dfn[a],t);
					}else{
						update(1,1,n,dfn[top[b]],dfn[b],t);
						b=top[b];
						if(fa[b]!=0){
							b=fa[b];
						}
						//update(1,1,n,dfn[b],dfn[b],t);
					}
				}
				if(dfn[a]>dfn[b]){
					swap(a,b);
				}
				update(1,1,n,dfn[a],dfn[b],t);
			}else{
				int ans=0;
				while(top[a]!=top[b]){
					if(dep[top[a]]>dep[top[b]]){
						ans+=query(1,1,n,dfn[top[a]],dfn[a]).sum;
						a=top[a];
						if(fa[a]!=0){
							if(query_color(1,1,n,dfn[a])==query_color(1,1,n,dfn[fa[a]])){
								ans++;
							}
							a=fa[a];
						}
					}else{
						ans+=query(1,1,n,dfn[top[b]],dfn[b]).sum;
						b=top[b];
						if(fa[b]!=0){
							if(query_color(1,1,n,dfn[b])==query_color(1,1,n,dfn[fa[b]])){
								ans++;
							}
							b=fa[b];
						}
					}
				}
				if(dfn[a]>dfn[b]){
					swap(a,b);
				}
				ans+=query(1,1,n,dfn[a],dfn[b]).sum;
				cout<<ans<<"\n";
			}
		}
	}
	return 0;
}