[WC2011]最大XOR和路径

\(\text{Solution}\)

通过观察发现答案路径为一条链和一些简单环组成
环可选可不选，可用过线性基决定（异或最大值）
链的选择不影响答案（考虑多条链必然产生环，涉及的环的异或值是同样的）
那么我们就只要任取一条链并借助返祖边找到简单环，线性基弄出答案即可

\(\text{Code}\)

#include <cstdio>
#include <iostream>
#define IN inline
#define RE register
#define LL long long
using namespace std;

const int N = 1e5 + 5;
int n, m, tot, h[N], vis[N];
LL dis[N];
struct edge{int to, nxt; LL w;}e[N << 1];
IN void add(int x, int y, LL z){e[++tot] = edge{y, h[x], z}, h[x] = tot;}

LL p[N];
IN void insert(LL x)
{
	for(RE int i = 61; i >= 0; i--)
	if ((x >> i) & 1)
		if (!p[i]){p[i] = x; return;}
		else x ^= p[i];
}
IN void dfs(int x, LL d)
{
	vis[x] = 1, dis[x] = d;
	for(RE int i = h[x]; i; i = e[i].nxt)
	{
		int v = e[i].to;
		if (!vis[v]) dfs(v, d ^ e[i].w);
		else if (e[i].w ^ dis[x] ^ dis[v]) insert(e[i].w ^ dis[x] ^ dis[v]);
	}
}

int main()
{
	scanf("%d%d", &n, &m); LL w;
	for(RE int i = 1, u, v; i <= m; i++) scanf("%d%d%lld", &u, &v, &w), add(u, v, w), add(v, u, w);
	dfs(1, 0); LL ans = dis[n];
	for(RE int i = 61; i >= 0; i--) ans = max(ans, ans ^ p[i]);
	printf("%lld\n", ans);
}