只 AC 测试点 7-10，实在调不动了

说到做到，只支持VX支付

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#define il inline 
#define lc p<<1
#define rc p<<1|1
using namespace std;
int n,m;
const int N=100005;
vector<int> e[N];
struct tree{
	int l,r,lcol,rcol,sum,add;
}t[N<<2];
int fa[N],son[N],dep[N],siz[N],w[N];
int dfn[N],wt[N],tops[N],tot=0,c=0;
int Lc,Rc;

il void pushup(int p){
	t[p].sum=t[lc].sum+t[rc].sum;
	if(t[lc].rcol==t[rc].lcol)	t[p].sum++;
	t[p].lcol=t[lc].lcol;
	t[p].rcol=t[rc].rcol;
}

il void build(int p,int x,int y){
	t[p].l=x;
	t[p].r=y;
	t[p].sum=t[p].add=0;
	if(x==y){
		t[p].lcol=t[p].rcol=wt[x];
		return ;
	}
	int mid=(x+y)>>1;
	build(lc,x,mid);
	build(rc,mid+1,y);
	pushup(p);
}

il void pushdown(int p){
	if(t[p].add){
		t[lc].sum=(t[lc].r-t[lc].l);
		t[rc].sum=(t[rc].r-t[rc].l);
		t[lc].lcol=t[lc].rcol=t[p].add;
		t[rc].lcol=t[rc].rcol=t[p].add;
		t[lc].add=t[p].add;
		t[rc].add=t[p].add;
		t[p].add=0;
	}
}

il void update(int p,int x,int y,int k){
	if(x<=t[p].l && t[p].r<=y){
		t[p].sum=t[p].r-t[p].l;
		t[p].lcol=t[p].rcol=k;
		t[p].add=k;
		return ;
	}
	pushdown(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(x<=mid) update(lc,x,y,k);
	if(y>mid) update(rc,x,y,k);
	pushup(p);
}

il int query(int p,int x,int y){
	if(t[p].l==x) Lc=t[p].lcol;
	if(t[p].r==y) Rc=t[p].rcol;
	if(x<=t[p].l && t[p].r<=y) return t[p].sum;
	int res=0,opt=0;
	pushdown(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(x<=mid) res+=query(lc,x,y),opt++;
	if(y>mid) res+=query(rc,x,y),opt++;
	if(opt==2 && t[lc].rcol==t[rc].lcol) res++; 
	return res;
}

il void dfs1(int x,int f){
	fa[x]=f;
	dep[x]=dep[f]+1;
	siz[x]=1;
	int maxson=-1;
	for(auto y:e[x]){
		if(y==f) continue;
		dfs1(y,x);
		siz[x]+=siz[y];
		if(siz[y]>maxson) maxson=siz[y],son[x]=y;
	}
}

il void dfs2(int x,int topf){
	tops[x]=topf;
	dfn[x]=++tot;
	wt[tot]=w[x];
	if(!son[x]) return ;
	dfs2(son[x],topf);
	for(auto y:e[x]){
		if(y==fa[x] || y==son[x]) continue;
		dfs2(y,y);
	}
}

il void sol1(int x,int y){
	++c;
	while(tops[x]!=tops[y]){
		if(dep[tops[x]]<dep[tops[y]]) swap(x,y);
		update(1,dfn[tops[x]],dfn[x],c);
		x=fa[tops[x]];
	}
	if(dep[x]<dep[y]) swap(x,y);
	update(1,dfn[y],dfn[x],c);
}

il int sol2(int x,int y){
	int res=0,ans1=-3274282,ans2=-3274282;
	while(tops[x]!=tops[y]){
		if(dep[tops[x]]!=dep[tops[y]]){
			swap(x,y);
			swap(ans1,ans2);
		}
		res+=query(1,dfn[tops[x]],dfn[x]);
		if(ans1==Rc) res++;
		ans1=Lc;
		x=fa[tops[x]];
	}
	if(dep[x]<dep[y]){swap(x,y);swap(ans1,ans2);}
	res+=query(1,dfn[y],dfn[x]);
	if(ans1==Rc) res++;
	if(ans2==Lc) res++;
	return res;
}

il void clea(){
	for(int i=1;i<=n;++i) e[i].clear();
	tot=c=0;
	memset(w,0,sizeof(w));
	memset(t,0,sizeof(t));
	memset(dfn,0,sizeof(dfn));
	memset(siz,0,sizeof(siz));
	memset(fa,0,sizeof(fa));
	memset(tops,0,sizeof(tops));
	memset(son,0,sizeof(son));
	memset(dep,0,sizeof(dep));
	memset(wt,0,sizeof(wt));
}

il void mian(){
	scanf("%d%d",&n,&m);
	clea();
	for(int i=1;i<n;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int i=1;i<=n;++i) w[i]=++c;
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	while(m--){
		int opt,x,y;
		scanf("%d%d%d",&opt,&x,&y);
		if(opt==1) sol1(x,y);
		else printf("%d\n",sol2(x,y));
	}
}

int main(){
	int T; scanf("%d",&T);
	while(T--) mian();
}