自动搬运

查看原文

来自洛谷，原作者为

	小毓 平静

搬运于2025-08-24 22:32:36，当前版本为作者最后更新于2021-07-26 22:38:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

大家好啊！作为一个蒟蒻，能在线上同步赛的时候把这题做出来，我的心里可是万分欣喜的啊！（大佬勿嘲）

好了，话不多说，我来与大家分享一下我的想法。（可能有点啰嗦）

看到这个题，树上的路径操作并查询，那不就是树剖么？心里顿时有了底。可是仔细读题，发现并不是单纯地路径操作，还会涉及到对于每个点邻边的修改。这怎么搞？貌似单纯直白的树剖并不能解决问题。这条路能否走通呢？

其实是能的。我们对问题进行一个简单而巧妙的转化，就能解决！如果我们在每次操作的时候，将修改路径上的点全部染上一种独一无二的颜色，判断重边就只需要判断两端点颜色是否相同即可。端点颜色相同为重边，否则为轻边。

如果您懂了，就可以跳过下面这段话。

没有太懂的话，具体的讲一讲，因为要将一条路径上的边修成重边，那么路径点染同色的操作就可以保证这条路径上点同色且所有边两端点同色，这样这些边就符合重边的判定了！而且更妙的是，由于这些点被染成的是一种独一无二的颜色，是一定不与前面的颜色重复的，所以所有染色点连边的另一端一定与它的颜色不同，这样子这些边就自然而然的变成了轻边。这个转化不得不说是很精妙的。

于是，问题变成了：

如何统计树的一段路径上同色相邻点对的数量？（相邻：保证两点有边；同色：保证是重边）

这里提供一种线段树维护的经典方法：对于每个节点建立结构体，分别存储三个信息：该区间左端点颜色、该区间右端点颜色、该区间内同色相邻点对数量。这样在合并的时候，通过比较两区间接头处颜色的情况，来更新新的区间答案。具体可以看看代码，里面有详尽的注释和陷阱的提醒（码风巨丑不喜可调）

哦哦，另外补充一下，这个题的代码中树剖区间查询可以说是一大重难点。因为我们需要查询区间左右“有序”，所以我们会设置两个答案变量$ans1$和$ans2$，分别以下图的方式从两头统计答案，最后再合并。还是看代码吧大家~~

#include <cstring>
#include <cstdio>
const int MX=100005;
int n,ind,fir[MX],deep[MX],idx[MX],topf[MX],son[MX],sz[MX],fa[MX];
struct Edge{int to,nxt;}e[MX<<1];
struct Node{int lc,rc,cnt;void cln(){lc=rc=cnt=0;}};
//Node结构体中：lc左颜色，rc右颜色，cnt个数 
struct Segtree{
	int lazy[MX<<2];Node tree[MX<<2];
	void cln(){
		//线段树内清空 
	    memset(lazy,0,sizeof lazy);
		for(int i=0,h=MX<<2;i<h;i++)tree[i].cln();	
	}
	void lazy_down(int k,int l,int r){
		//懒标记下传 
		if(!lazy[k])return;
		int x=lazy[k],mid=(l+r)>>1;lazy[k]=0;
		lazy[k<<1]=lazy[k<<1|1]=x;
		tree[k<<1]=(Node){x,x,mid-l};
		//为什么是mid-l？因为一共有mid-l+1个点都被染成颜色x，所以考虑间隔有mid-l对 
		tree[k<<1|1]=(Node){x,x,r-mid-1};
		//为什么是r-mid-1？理由同上啦 
	}
	void update(int ul,int ur,int nl,int nr,int pos,int num){
		if(ul<=nl&&nr<=ur){
			tree[pos]=(Node){num,num,nr-nl};
			//为什么是nr-nl？理由在lazy_down函数里啦 
			lazy[pos]=num;return;
		}
		lazy_down(pos,nl,nr);int mid=(nl+nr)>>1;
		if(ul<=mid)update(ul,ur,nl,mid,pos<<1,num);
		if(mid<ur)update(ul,ur,mid+1,nr,pos<<1|1,num);
		Node ls=tree[pos<<1],rs=tree[pos<<1|1];
		tree[pos]=(Node){
			ls.lc,rs.rc,ls.cnt+rs.cnt+(ls.rc==rs.lc)
		};
		//关键↑区间合并，应该比较好懂，关键在于左儿子的右颜色
		//和右儿子的左颜色相同时，需要将计数器加一 
	}
	Node query(int al,int ar,int nl,int nr,int pos){
		if(al<=nl&&nr<=ar)return tree[pos];
		lazy_down(pos,nl,nr);int cnt=0,mid=(nl+nr)>>1;Node w1,w2;
		//cnt负责控制查询情况种类，见下↓ 
		if(al<=mid){cnt++;w1=query(al,ar,nl,mid,pos<<1);}
		if(mid<ar){cnt+=2;w2=query(al,ar,mid+1,nr,pos<<1|1);}
		if(cnt==1)return w1;if(cnt==2)return w2;
		return (Node){
			w1.lc,w2.rc,w1.cnt+w2.cnt+(w1.rc==w2.lc)
		};
		//同样是关键的合并，同update函数操作 
	}
}sgtree;
void add(int a,int b,int pos){
	e[pos]=(Edge){b,fir[a]};fir[a]=pos;
}
//建边 
void swp(int& a,int& b){int t=a;a=b;b=t;}
//手写交换swap函数 
void all_cln(){
	//这个函数是掌管清空的，多组数据一定要小心！
	//建议：能清的都清了，免得出现什么奇怪的错误 
	ind=0;sgtree.cln();
	memset(sz,0,sizeof sz);
	memset(fa,0,sizeof fa);
	memset(idx,0,sizeof idx);
	memset(fir,0,sizeof fir);
	memset(son,0,sizeof son);
	memset(topf,0,sizeof topf);
	memset(deep,0,sizeof deep);
}
void dfs1(int x,int f,int d){
	deep[x]=d;fa[x]=f;sz[x]=1;
	for(int i=fir[x];i;i=e[i].nxt){
		int h=e[i].to;
		if(h!=f){
			dfs1(h,x,d+1);sz[x]+=sz[h];
			if(sz[h]>sz[son[x]])son[x]=h;
		}
	}
}
//树剖常规第一遍dfs 
void dfs2(int x,int tp){
	if(!x)return;topf[x]=tp;
	idx[x]=++ind;dfs2(son[x],tp);
	for(int i=fir[x];i;i=e[i].nxt){
		int h=e[i].to;if(h!=son[x]&&h!=fa[x])dfs2(h,h);
	}
}
//树剖常规第二遍dfs 
void range_update(int x,int y,int num){
	while(topf[x]!=topf[y]){
		int tx=topf[x],ty=topf[y];
		if(deep[tx]<deep[ty]){swp(x,y);swp(tx,ty);}
		sgtree.update(idx[tx],idx[x],1,n,1,num);
		x=fa[tx];
	}
	if(deep[x]<deep[y])swp(x,y);
	sgtree.update(idx[y],idx[x],1,n,1,num);
}
//树剖区间修改 
int range_query(int x,int y){
	//树剖的区间查询，可以说是整个程序的大核心，一定要深刻理解
	//建议画图辅助思考，会有一定难度 
	bool flg=0;//flg表示当前答案应归到哪边，0为ans1,1为ans2 
	Node h,ans1=(Node){0,0,0},ans2=(Node){0,0,0};
	while(topf[x]!=topf[y]){
		int tx=topf[x],ty=topf[y];
		if(deep[tx]<deep[ty]){flg=!flg;swp(tx,ty);swp(x,y);}
		//记得同时取反flg 
		h=sgtree.query(idx[tx],idx[x],1,n,1);
		//以下是最核心部分↓
		//请大家一定注意：每次的查询h，一定是左端点在深度小的地方，
		//右端点在深度大的地方，所以千万不能把左右端点合并错 
		if(flg)
		    ans2=(Node){
				h.lc,ans2.rc,ans2.cnt+h.cnt+(ans2.lc==h.rc)
			};
		//ans2情况 
		else
			ans1=(Node){
				ans1.lc,h.lc,ans1.cnt+h.cnt+(ans1.rc==h.rc)
			};
		//ans1情况 
		x=fa[tx];
	}
	if(deep[x]<deep[y]){swp(x,y);flg=!flg;}
	h=sgtree.query(idx[y],idx[x],1,n,1);
	if(flg)
	    ans2=(Node){
			h.lc,ans2.rc,ans2.cnt+h.cnt+(ans2.lc==h.rc)
		};
	else
		ans1=(Node){
			ans1.lc,h.lc,ans1.cnt+h.cnt+(ans1.rc==h.rc)
		};
	//末处理 
	return ans1.cnt+ans2.cnt+(ans1.rc==ans2.lc);
}
int main(){
	//freopen("edge.in","r",stdin);
    //freopen("edge.out","w",stdout);
	int data;scanf("%d",&data);
	for(int i=1;i<=data;i++){
		all_cln();//别忘了清空！！ 
		int m;scanf("%d%d",&n,&m);
		for(int j=1;j<n;j++){
			int a,b;scanf("%d%d",&a,&b);
			add(a,b,j);add(b,a,j+n-1);
		}
		dfs1(1,0,1);dfs2(1,1);
		for(int j=1;j<=n;j++)sgtree.update(idx[j],idx[j],1,n,1,-idx[j]);
		//上面这句也很重要，先把每个点起始赋一个互不相同的值，
		//随便你赋啥 
		for(int j=1;j<=m;j++){
		    int opt,a,b;
			scanf("%d%d%d",&opt,&a,&b);
			if(opt&1)range_update(a,b,j);
			//以询问编号j作为“独一无二的颜色” 
			else printf("%d\n",range_query(a,b));
		}
	}
	//fclose(stdin);
    //fclose(stdout);
	return 0;
}

这里，再给大家送一道题： P2486 染色

这道题也是线段树信息维护的经典运用，和本题转化后基本类似，大家可以去试试哟。

谢谢大家！