自动搬运

查看原文

来自洛谷，原作者为

	Yannik **

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

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

以下是正文

题意：

任意选两个不同的点使得其路径的异或和最小。求出这个值。

思路：

先考虑任意两个点 $x$ 到 $y$ 的任意一条简单路径。可以通过直接遍历得到，再考虑如何是异或和最小。必然是多走一些路。一个可行的方法是：从某一个点开始走到一个环，在环上走一圈，回到这个点。然后枚举所有环，把环的异或值插入线性基，用线性基跑最小值即可。

Tips：

• 求任意两点简单路径异或和：比如 $a$ 到 $b$ 的异或和为 $x$，$a$ 到 $c$ 的异或和为 $y$。则 $b$ 到 $c$ 的异或和为 $x$ $⊕$ $y$。
• 那么一个环的异或和呢？把上面那个 $c$ 改成 $b$ 即可。即 $b$ 再走回 $b$，不就是一个环吗？

void dfs(int u,int fa){
	for(auto x:g[u]){
		int e=x.first,w=x.second;
		if(vis[e]){
			ins(xo[e]^xo[u]^w);//环的异或和
		} else {
		    vis[e]=1;
			tmp.push_back(e);
			xo[e]=xo[u]^w;
			dfs(e,u);
		}
	}
}

• 注意两个点之间可能不连通。需要多次遍历。
• 线性基求最小值贪心即可。

int res=xo[x]^xo[y];
for(int k=31;~k;k--){
    if((res^p[k])<res) res=res^p[k];
}
ans=min(ans,res);

$\tiny 谢谢你的观看。$