题目解法：树链剖分 + 线段树维护路径颜色段

题目大意

给定一棵树，初始所有边为轻边。支持两种操作：

1. 路径重染色：将路径 $a \to b$ 上所有点相连的边先变成轻边，再将路径 $a \to b$ 上的边变成重边。

2. 查询路径重边数量：询问路径 $a \to b$ 上有多少条重边。

算法思路

1.问题转化

• 将边的信息存储到深度较大的节点上（树链剖分常用技巧）。

• 对于操作 1，相当于：

  第一步：将路径 $a \to b$ 上所有点（包括端点）的所有邻边变为轻边 → 即这些点的所有子边和父边都变轻。

  第二步：将路径 $a \to b$ 上的边变为重边。

• 实际上，我们可以将每条边用一个颜色表示，不同操作赋予不同颜色（用操作编号 $i$ 作为颜色），这样就能区分不同时间设置的重边。

2. 树链剖分

通过两次 DFS 将树剖分成链，得到 dfn（DFS 序）、top（链顶）、son（重儿子）等数组。

这样任意路径可以拆成 $O(\log n)$ 段连续的 DFS 序区间。

3. 线段树维护颜色段

线段树节点维护：

l：区间左端点的颜色

r：区间右端点的颜色

cnt：区间内颜色段交界数量（即相邻不同色的次数）

tag：懒标记，表示区间被整体染色

合并两个区间时：

总 cnt = cnt左 + cnt右 + (左.r == 右.l && 左.r != 0) 即如果左区间右端和右区间左端颜色相同且非 0，则交界处不算新段。

4. 操作实现

操作 1：

• 用树链剖分将路径 $a \to b$ 上所有节点的 DFS 区间整体染色为当前操作编号 $i$（表示重边）。

• 注意：这里直接覆盖了之前的所有邻边信息，相当于先清空邻边再设置路径边。

操作 2：

• 将路径 $a \to b$ 拆成 $x \to lca$ 和 $y \to lca$ 两部分。

• 分别查询两部分的颜色段信息，合并时判断连接处颜色是否相同。

• 路径上的重边数 = 颜色段数 - 1（因为相邻同色段属于同一次操作设置的重边连续段）。

复杂度分析

树链剖分：$O(n)$

每次操作：$O(\log^2 n)$（树链剖分路径拆分 × 线段树区间查询/修改）

总复杂度：$O(m \log^2 n)$，可过 $n,m \le 10^5$。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ls x<<1
#define rs x<<1|1
const int N=1e5+5;
int t,n,m,cnt;
int siz[N],dep[N],fa[N],dfn[N],son[N],top[N];
vector<int> e[N];
struct tree{
	int l,r,cnt,tag;
	friend tree operator+(tree x,tree y){
		x.cnt+=y.cnt+(x.r==y.l&&x.r);
		x.r=y.r;
		x.tag=0;
		return x;
	}
}tr[4*N];
void lazy(int x,int l,int r,int v){
	tr[x]={v,v,r-l,v};
}
void pushdown(int x,int l,int r){
	// cerr<<x<<endl;
	if(!tr[x].tag) return ;
	int mid=l+r>>1;
	lazy(ls,l,mid,tr[x].tag);
	lazy(rs,mid+1,r,tr[x].tag);
	tr[x].tag=0;
}
void build(int x,int l,int r){
	tr[x]={0,0,0,0};
	if(l==r) return ;
	int mid=l+r>>1;
	build(ls,l,mid),build(rs,mid+1,r);
}
void update(int x,int l,int r,int L,int R,int v){
	if(L<=l&&R>=r) return lazy(x,l,r,v);
	pushdown(x,l,r);
	int mid=l+r>>1;
	if(L<=mid) update(ls,l,mid,L,R,v);
	if(R>=mid+1) update(rs,mid+1,r,L,R,v);
	tr[x]=tr[ls]+tr[rs];
}
tree query(int x,int l,int r,int L,int R){
	// cerr<<x<<" "<<l<<" "<<r<<" "<<L<<" "<<R<<endl;
	if(L<=l&&R>=r) return tr[x];
	pushdown(x,l,r);
	int mid=l+r>>1;
	if(R<=mid) return query(ls,l,mid,L,R);
	if(L>=mid+1) return query(rs,mid+1,r,L,R);
	return query(ls,l,mid,L,R)+query(rs,mid+1,r,L,R);
}
void dfs1(int x,int fax){
	fa[x]=fax,dep[x]=dep[fax]+1;
	siz[x]=1;
	for(int y:e[x]){
		if(y==fax) continue;
		dfs1(y,x);
		siz[x]+=siz[y];
		if(siz[y]>siz[son[x]]) son[x]=y;
	}
}
void dfs2(int x,int tp){
	dfn[x]=++cnt,top[x]=tp;
	// cerr<<x<<" "<<cnt<<" "<<tp<<endl;
	if(son[x]) dfs2(son[x],tp);
	for(int y:e[x]){
		if(y==fa[x]||y==son[x]) continue;
		dfs2(y,y);
	}
}
void upd(int x,int y,int v){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		update(1,1,n,dfn[top[x]],dfn[x],v);
		x=fa[top[x]];
	}
	if(dep[y]<dep[x]) swap(x,y);
	update(1,1,n,dfn[x],dfn[y],v);
}
void qry(int x,int y){	
	bool f=0;
	int lca=0,xx=x,yy=y;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y),f^=1;
		x=fa[top[x]];
	}
	if(dep[x]<dep[y]){
		lca=x;
		if(f) x=xx,y=yy;
		else x=yy,y=xx;
	}else {
		lca=y;
		if(!f) x=xx,y=yy;
		else x=yy,y=xx;
	}
	// cerr<<"A"<<lca<<endl;
	// cerr<<x<<" "<<y<<'\n';
	tree tmpx={0,0,0,0},tmpy={0,0,0,0};
	while(top[x]!=top[lca]){
		tmpx=query(1,1,n,dfn[top[x]],dfn[x])+tmpx;
		x=fa[top[x]];
	}
	// cerr<<query(1,1,n,dfn[top[x]],dfn[x]).cnt<<'\n';
	tmpx=query(1,1,n,dfn[lca],dfn[x])+tmpx;
	// cerr<<tmpx.l<<" "<<tmpx.r<<" "<<tmpx.cnt<<'\n';
	while(y!=lca){
		tmpy=query(1,1,n,dfn[top[y]],dfn[y])+tmpy;
		y=fa[top[y]];
	}
	cout<<tmpx.cnt+tmpy.cnt+(tmpx.l==tmpy.l&&tmpx.l)<<'\n';
}
void init(){
	for(int i=1;i<=n;i++){
		e[i].clear();
		dep[i]=son[i]=top[i]=0;
	}
	cnt=0;
}
void solve(){
	init();
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs1(1,0);
	dfs2(1,1);
	// for(int i=1;i<=n;i++){
	// 	cout<<dfn[i]<<" ";
	// }
	// cout<<'\n';
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int op,a,b;
		cin>>op>>a>>b;
		if(op==1){
			upd(a,b,i);
		}else{
			qry(a,b);
		}
	}
}
int main(){
	//freopen("edge.in","r",stdin);
	//freopen("edge.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cin>>t;
	while(t--) solve();
	return 0;
}