P4151 [WC2011]最大XOR和路径
滑稽的小宫
·
·
题解
前言
翻这道题题解的时候看到了 @caeious 大佬的题解，别的题解都没有进行严格证明为什么不用找全部的环就可以表出全部的环，但这位大佬给出了详细的证明，但由于他的证明完全从数学角度出发，蒟蒻花了很久才明白，因此在这里从感性理解的角度来讲一讲 @caeious 大佬的方法
题意：
在无向图上找出一条不一定简单（简单指不重复经过一个节点）的路径，使得路径上值的异或和最大（多次经过一个节点在异或和中要多次计算这个节点的值）
一些约定与定义
为了方便叙述，有以下定义
- T：图的任意一棵生成树
-
-
-
f(u)$ ：生成树上从1到u的简单路径值的异或和，即 $f(u)=w(t(u))
理论分析
定理1： 设一个集合 A=\{f(u)\oplus w(u,v)\oplus f(v)|(u,v)\in E\}（即从1到u再沿着一条边到v再到1的异或和），则从1出发走一段路最后回到1的路径的异或和就可以表示为A集合中一些元素的异或和。
考虑一下如果有一条从1出发回到1的路径经过了 1,p_1,p_2,p_3,1 节点（如上图），那么我们可以先算从1到 p_1 到 p_2 到1的路径，异或上从1到 p_2 到 p_3 到1的路径，由于异或的性质，这里面1到 p_2 的路径就被抵消了，因此最终结果就是：从1到 p_1 到 p_2 到 p_3 到1的路径
在上图中就是蓝色路径走了两次异或和抵消了，因此最后只剩下了外面一圈的路径异或和。
所以任何一条从1到1的路径都可以表示成A集合内某些元素的异或和。
定理2： 设集合B为所有从1到n的路径的异或和（即答案所求），集合C为所有从1到1路径的异或和异或上 f(n) 的值构成的集合，即 C=\{val*f(n)|val\in A\}，那么有 B=C
$B\subseteq C$ ：如果一条路径 $p$ 是从1出发到n（属于B集合），那么 $w(p)\oplus f(n)\oplus f(n)=w(p)$ ，而 $w(p)\oplus f(n)$ 相当于一条从1到n再走到1的路径的异或和，因此就可以把这条从1出发到n的路径变为从1出发到n，再沿着生成树上边到1，再原路返回n的路径的异或和，而从1出发到n再到1显然是A集合的一条路径，因此任意一条B包含的路径都是C包含的一条路径
## 算法实现
综上，就可以得出一个这样的算法：
用 $A=\{f(u)\oplus w(u,v)\oplus f(v)|(u,v)\in E\}$ 这个集合里面的值组合得到一个异或和，使得和 $f(n)$ 异或的值最大，这个最大值就是答案。
显然可以用线性基进行计算，把所有 $f(u)\oplus w(u,v)\oplus f(v)$ 塞进线性基，算出线性基以后从高位到低位考虑异或 $f(n)$ 之后能不能变大即可。
## 代码
```cpp
#include<iostream>
#include<cstdio>
#define N 50010
#define M 100010
#define ll long long
int tot,n,m,hd[N],to[2*M],nxt[2*M],cnt;
ll f[N],val[2*M],a[2*M];//f数组同上述解释，a数组储存A集合元素
bool vis[N],vi[N];
void newedge(int u,int v,ll w){
nxt[++tot]=hd[u];
to[tot]=v,val[tot]=w;
hd[u]=tot;
return;
}void dfs(int x){//求出f数组
vis[x]=1;
for(int i=hd[x];i;i=nxt[i]){
int nex=to[i];
if(vis[nex])continue;
f[nex]=f[x]^val[i];
dfs(nex);
}return;
}void swap(ll &x,ll &y){
ll tmp=x;
x=y,y=tmp;
return;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
ll u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
newedge(u,v,w);
newedge(v,u,w);
}dfs(1);
/*将A集合元素加入，准备计算线性基
for(int x=1;x<=n;x++)
for(int i=hd[x];i;i=nxt[i])
a[++cnt]=f[x]^val[i]^f[to[i]];
/*线性基部分*/
for(int bit=62,i=1;bit>=0;bit--){
bool flag=false;
for(int j=i;j<=cnt;j++){
if(a[j]&(1ll<<bit)){
swap(a[i],a[j]),flag=true;
break;
}
}if(!flag)continue;
for(int j=1;j<=cnt;j++)if(j!=i&&(a[j]&(1ll<<bit)))a[j]^=a[i];
i++;
}
/*寻找最大值*/
for(int i=1;i<=62;i++)
if((f[n]^a[i])>f[n])f[n]^=a[i];
printf("%lld",f[n]);
return 0;
}
```
**以上只是感性理解，建议大家去看看 @caeious 的理性证明的题解，非常有帮助！**