这道题啊，精妙。
第一会发现环是想走就走的。因此需要找到环，然后把环的异或值加入线性基。
再者发现只要将刚开始的 链的异或 在线性基里找到最大值就行。但是这条链是需要去寻找的吗？发现并不需要，因为可以发现如果有别的路径，那么两条路径就必定会产生一个环，那么在线性基里就可以通过异或（想当于改变初始认定的环）就行了。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6;
struct edge{
ll to,w,ne;
}e[N];
int cnt;
int head[N];
ll g[61];
void add(ll x){
for(int i=60;i>=0;i--)if((x>>i)&1){
if(!g[i]){
g[i]=x;
break;
}
x^=g[i];
}
}
ll s_max(ll ean){
for(int i=60;i>=0;i--){
ean=max(ean,ean^g[i]);
}
return ean;
}
void init(){
memset(head,-1,sizeof head);
}
void addedge(ll a,ll b,ll w){
e[cnt].to=b;
e[cnt].w=w;
e[cnt].ne=head[a];
head[a]=cnt++;
}
ll pre[N];
ll vis[N];
void dfs(int x,ll res){
pre[x]=res;
for(int i=head[x];~i;i=e[i].ne){
int u=e[i].to;
if(!vis[u]){
vis[u]=1;
dfs(u,res^e[i].w);
}else{
add(res^e[i].w^pre[e[i].to]);
}
}
}
int main(){
init();
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y;ll w;
cin>>x>>y>>w;
addedge(x,y,w);
addedge(y,x,w);
}
dfs(1,0);
cout<<s_max(pre[n])<<endl;
}
原文：https://www.cnblogs.com/Ean1zhi/p/13388174.html