自动搬运

查看原文

来自洛谷，原作者为

	Crab_Dave 老博客了，鸽子在东西

搬运于2025-08-24 22:12:58，当前版本为作者最后更新于2019-11-14 07:58:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

考场上挂了，想到了生成树，但没想到正解qwq

题中有一句话十分重要——

保证$G$中不存在简单环使得边权异或和不为$0$。

这句话是什么意思呢？

$G$中的环（如果存在）边权异或和都为$0$！

那我们走环干啥qwq

对啊，那我们走环干啥！

不走了呗

对啊，不走了呗！

另外，从一条路径增广到另一条路径的必要条件（应该是必要条件吧，反正逻辑什么的口胡一下就行2333）是这两条路径能够成一个环。

在这道题中，就是这两条路径的权值 异或和为$0$。

那不就是相等吗？

是啊，就是这两条路径相等啊！

推广一下这个结论，我们可以得到一个看似口胡的结论（当然只适用于这道题）——

$(x,y)$之间任一路径权值相等，即所有路径等价。

好了，大功告成！

随便求棵生成树，dfs$O(n)$预处理，$O(q)$询问，完毕~

详见代码qwq

#include<cstdio>
using namespace std;

int n,m,q,fa[100005],s[100005];
int head[100005],k=1;
struct edge
{
	int to,next,w;
}e[400005],eg[200005];//存边
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}//并查集带路径压缩的查找

void adde(int u,int v,int w)//链式前向星加边
{
	e[k].to=v;
	e[k].w=w;
	e[k].next=head[u];
	head[u]=k++;
}

void Produce()//求生成树
{
	for(register int i=1;i<=n;i++)fa[i]=i;//并查集初始化
	for(register int i=1;i<=m;i++)
	{
		int fu=find(eg[i].next),fv=find(eg[i].to);//一条边两个端点的父亲
		if(fu==fv)continue;//如果父亲相同，则已经联通，再连边就会成环
		fa[fu]=fv;//合并两点
		adde(eg[i].next,eg[i].to,eg[i].w);//加边
		adde(eg[i].to,eg[i].next,eg[i].w);
	}
}

void dfs(int u,int fa)//dfs预处理异或和
{
	for(register int i=head[u];i;i=e[i].next)//遍历子节点
	{
		int v=e[i].to;
		if(v==fa)continue;//父亲则跳过
		s[v]=s[u]^e[i].w;//s[i]表示i到根节点的距离
		dfs(v,u);//继续深搜
	}
}

int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(register int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		eg[i]=(edge){u,v,w};//先暂时存一下边
	}
	Produce();//求生成树
	dfs(1,0);//预处理
	while(q--)
	{
		int x,y;
		scanf("%d%d",&x,&y);//读入x,y
		printf("%d\n",s[x]^s[y]);//s[x]和s[y]异或时，lca(x,y)及以上的部分就抵消掉了，只留下最短路上的点
	}
	return 0;//结束了罪恶的一生
}

求资瓷qwq