不妨先了解几个前置知识/引理：
异或的抵消性质：
- \(a\oplus a=0\)
- \(\forall b[b\not= a],a\oplus b\not=0\)
- \((a\oplus b)\oplus (a\oplus c)=b\oplus c\)
引理 \(1\)：\(\forall u,v\in\text{Tree}\)，\(u\to v\) 所有路径的边权异或和都等于 \(dis_u\oplus dis_v\)（\(dis_i\) 为节点 \(i\) 到根路径上边权的异或和）
上述引理根据异或的抵消性可得。
引理 \(2\)：对于一般图 \(G\)，我们任取一颗 \(\text{DFS}\) 树。那么图上所有的环都可以用只包含了一条非树边的简单环异或出来。
引理 \(3\)：对于图上两点间的任意路径（我们只关心边权的异或和），必定可以由 \(\text{DFS}\) 树上的树边路径以及图中一些环异或出来。
依旧是利用异或的抵消性质得到。
我们回到题目中。假设输入的图是一棵树，那么直接 \(dis_1\oplus dis_n\) 就做完了。
但输入的可能是一般图——我们任取一颗 \(\text{DFS}\) 树，按照上述方法求出 \(dis_1\) 到 \(dis_n\)。之后考虑那些非树边，每条非树边都必定会与一些树边形成恰好一个简单环。根据引理 \(2,3\)，我们只需要维护一个支持插入的数据结构，它能选出一个子集，使得子集中的元素异或上 \(dis_1\oplus dis_n\) 最大。发现线性基可以轻松的维护。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); i++)
#define FR(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
struct E{int v; ll w;}; vector<E> e[N];
int n, m, vis[N]; ll dis[N];
struct LinearBasis{
ll a[65];
int insert(ll x){
FR(i, 62, 0) if((x >> i) & 1){
if(!a[i]){a[i] = x; return 1;}
else x ^= a[i];
}
return 0;
}
ll qmin(ll ret = 0){
FR(i, 62, 0) ret = min(ret, ret ^ a[i]);
return ret;
}
} b;
void dfs(int u, int fa){
vis[u] = 1;
for(const auto &p: e[u]) if(p.v != fa){
if(!vis[p.v])
dis[p.v] = dis[u] ^ p.w, dfs(p.v, u);
else b.insert(dis[u] ^ dis[p.v] ^ p.w);
}
}
int main(){
scanf("%d%d", &n, &m);
FL(i, 1, m){
int u, v; ll w;
scanf("%d%d%lld", &u, &v, &w);
e[u].emplace_back((E){v, w});
e[v].emplace_back((E){u, w});
}
dfs(1, 0);
printf("%lld\n", b.qmin(dis[1] ^ dis[n]));
return 0;
}