树剖 10 分求助

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=114514;
int n,m;
vector<int> g[N];	//存储整个树  
int fa[N],son[N];	//父亲和重儿子 
int siz[N];	//子树大小 
int top[N];	//重链顶端 
int dfn[N],idx=0;	//idx 是 dfn 的时间戳 
int dep[N];	//记录节点的深度  
void dfs1(int u){
	siz[u]=1;
//	dfn[u]=++idx;
	int max_=0;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(fa[u]==v)	continue;
		fa[v]=u;
		dep[v]=dep[u]+1;
		dfs1(v);
		siz[u]+=siz[v];
		if(siz[v]>max_){
			max_=siz[v],son[u]=v;
		}
	}
}
void dfs2(int u,int top_){
	dfn[u]=++idx;
	top[u]=top_;
	if(son[u])	dfs2(son[u],top_);
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(fa[u]==v||son[u]==v)	continue;
		dfs2(v,v);
	}
}
struct node{
	int l,r;
	int lcol,rcol;	//左右区间的颜色  
	int tag;	//标记戳  
	int ans;	//子区间的答案  
}tree[4*N];
//void pushdown(int id){
//	if(tree[id].tag){
//		tree[id*2].tag=tree[id].tag;
//	}
//	
//}
//void findcol(int id,int x){
//	int l1=tree[id].l,r1=tree[id].r;
//	pushdown(id);
//} 
void pushup(int id){
//	int x=tree[id*2].r,y=tree[id*2+1].l;
//	//查询 x 的颜色是否是 y 的颜色 
//	int x2=findcol(id,x),y2=findcol(id,y);	//寻找 x 和 y 的颜色  
	tree[id].lcol=tree[id*2].lcol,tree[id].rcol=tree[id*2+1].rcol; //上传标记 
	tree[id].ans=(tree[id*2].rcol==tree[id*2+1].lcol)+tree[id*2].ans+tree[id*2+1].ans; 
}
void build(int id,int l,int r){
	tree[id].l=l,tree[id].r=r;
	if(l==r){
		tree[id].tag=++idx;
//		cout<<id<<' '<<l<<' '<<r<<' '<<idx<<endl;
		tree[id].lcol=tree[id].rcol=idx;
		return;
	}
	int mid=l+r>>1;
	build(id*2,l,mid),build(id*2+1,mid+1,r);
	pushup(id);
//	cout<<'#'<<id<<' '<<tree[id].ans<<endl;
}
void pushdown(int id){
	if(tree[id].tag){
		tree[id*2].tag=tree[id].tag;
		tree[id*2].ans=tree[id*2].r-tree[id*2].l;
		tree[id*2].lcol=tree[id*2].rcol=tree[id].tag;
		tree[id*2+1].tag=tree[id].tag;
		tree[id*2+1].ans=tree[id*2+1].r-tree[id*2+1].l;
		tree[id*2+1].lcol=tree[id*2+1].rcol=tree[id].tag;
		tree[id].tag=0;
	}
}
void modify1(int id,int l,int r){
	int l1=tree[id].l,r1=tree[id].r;
//	cout<<l1<<' '<<r1<<endl;
	if(l1>=l&&r1<=r){
		tree[id].tag=idx;
		tree[id].lcol=tree[id].rcol=idx;
		tree[id].ans=tree[id].r-tree[id].l;// 3 4 5 6 7 //7-3=4 4 个间距 
		return; 
	}
	pushdown(id);
	int mid=l1+r1>>1;
	if(l<=mid)	modify1(id*2,l,r);
	if(r>mid)	modify1(id*2+1,l,r);
	pushup(id); 
}
void modify(int x,int y){
	idx++;
//	cout<<idx<<endl;
	while(top[x]!=top[y]){
		int newdepx=dep[fa[top[x]]];
		int newdepy=dep[fa[top[y]]];
		if(newdepx<newdepy){
			//此时先操作 y 
			int l=dfn[top[y]];
			int r=dfn[y];
//			cout<<'#'<<l<<' '<<r<<endl;
			modify1(1,l,r);
			y=fa[top[y]]; 
		}
		else{
			int l=dfn[top[x]],r=dfn[x];
//			cout<<'#'<<l<<' '<<r<<endl;
			modify1(1,l,r);
			x=fa[top[x]];
		}
	}
	int l=dfn[x],r=dfn[y];
	if(l>r)	swap(l,r);
//	cout<<'#'<<l<<' '<<r<<endl;
	modify1(1,l,r);
}
int query1(int id,int l,int r){
	int include13=0;
	int l1=tree[id].l,r1=tree[id].r;
	if(l1>=l&&r1<=r){
		return tree[id].ans;
	}
	pushdown(id);
	int mid=l1+r1>>1;
	if(l<=mid)	include13+=query1(id*2,l,r);
	if(r>mid)	include13+=query1(id*2+1,l,r);
	if(l<=mid&&r>mid){
		include13+=(tree[id*2].rcol==tree[id*2+1].lcol);//本题的考点所在  
	}
	pushup(id);
	return include13;
}
int findcol(int id,int p){
	int l1=tree[id].l,r1=tree[id].r;
	if(l1==r1)	return tree[id].lcol;
	pushdown(id);
	int mid=l1+r1>>1;
	if(p<=mid)	return findcol(id*2,p);
	else	return findcol(id*2+1,p);
}
int query(int x,int y){
	int include13=0;
	while(top[x]!=top[y]){
		int newdepx=dep[fa[top[x]]],newdepy=dep[fa[top[y]]];
		if(newdepx<newdepy){
			int l=dfn[top[y]];
			int r=dfn[y];
//			cout<<'*'<<l<<' '<<r<<endl;
			include13+=query1(1,l,r);
//			cout<<'*'<<l<<' '<<r<<endl;
//			cout<<'&'<<include13<<endl;
			int l1=dfn[fa[top[y]]];
			int col=findcol(1,l),col1=findcol(1,l1);
			include13+=(col==col1); 
			y=fa[top[y]];
		}
		else{
			int l=dfn[top[x]];
			int r=dfn[x];
			include13+=query1(1,l,r);
//			cout<<'*'<<l<<' '<<r<<' '<<top[x]<<endl;
//			cout<<'&'<<include13<<endl;
			int l1=dfn[fa[top[x]]];
			int col=findcol(1,l),col1=findcol(1,l1);
			include13+=(col==col1); 
			x=fa[top[x]];
		}
	}
	int l=dfn[x],r=dfn[y];
	if(l>r)	swap(l,r);
	include13+=query1(1,l,r);
//	cout<<'*'<<l<<' '<<r<<endl;
//	cout<<'&'<<include13<<endl;
	return include13; 
}
void solve(){
	idx=0;
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v),g[v].push_back(u);
	}
	dep[1]=1;
	dfs1(1),dfs2(1,1);
	idx=0;
//	for(int i=1;i<=n;i++){
//		cout<<'#'<<i<<' '<<fa[i]<<' '<<siz[i]<<' '<<son[i]<<' '<<top[i]<<' '<<dfn[i]<<endl;
//	}
	build(1,1,n);
	while(m--){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1){
			modify(x,y);
		}
		else	cout<<query(x,y)<<endl;
	}
	idx=0;
	for(int i=1;i<=n;i++){
		while(g[i].size())	g[i].pop_back();
		fa[i]=son[i]=siz[i]=top[i]=dfn[i]=dep[i]=0;
	}
}
int T;
signed main(){
//	freopen("edge.in","r",stdin);
//	freopen("edge.out","w",stdout);
	cin>>T;
	while(T--)	solve();
	return 0;
} //再给我两分钟 让我把记忆结成冰