计算1到n的一条路径使得路径上的值xor和最大。
先任意走一条路径计算xor和，然后dfs的时候处理出所有的环的xor和，这样对于所有的环的xor和求线性基，在任意走出的路径的xor和上贪心即可。
正确性显然，如果环与选择的路径有重合，那么重合的部分就会被xor两次，也就没有xor，相当于更改了一部分路径。如果环与选择的路径没有重合，那么相当于从路径上任意一个点到环上的一个点，跑一圈后从进入环的点原路返回，这样环的xor和就计算到了，而往返两次的路径也因为xor了两次相当于没有xor，就不用考虑了。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 50003;
const int M = 100003;
void read(int &k) {
k = 0; int fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = (k << 3) + (k << 1) + c - '0';
k = k * fh;
}
void readll(ll &k) {
k = 0; int fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = (k << 3) + (k << 1) + c - '0';
k = k * fh;
} struct node {int nxt, to; ll w;} E[M << 1];
int n, m, cnt = 0, point[N];
ll p[M * 10], a[63], d[N];
bool vis[N]; void ins(int x, int y, ll z) {E[++cnt].nxt = point[x]; E[cnt].to = y; E[cnt].w = z; point[x] = cnt;}
void _(int x) {
vis[x] = 1;
for(int i = point[x]; i; i = E[i].nxt) {
int v = E[i].to;
if (vis[v]) p[++cnt] = d[v] ^ d[x] ^ E[i].w;
else d[v] = d[x] ^ E[i].w, _(v);
}
}
int main() {
read(n); read(m);
int u, v; ll e;
for(int i = 1; i <= m; ++i) {
read(u); read(v); readll(e);
ins(u, v, e); ins(v, u, e);
}
cnt = 0;
_(1);
for(int i = 1; i <= cnt; ++i)
for(int j = 60; j >= 0; --j)
if ((p[i] >> j) & 1) {
if (!a[j]) {a[j] = p[i]; break;}
else p[i] ^= a[j];
}
ll ans = d[n];
for(int j = 60; j >= 0; --j)
if (!((ans >> j) & 1) && a[j])
ans ^= a[j];
printf("%lld\n", ans);
return 0;
}
又坑在位运算优先级上了QAQ，">>"运算符的优先级竟然没有"=="运算符的优先级高！我在位运算上再次犯逗1h+，比赛时再这么犯逗就真的要滚粗了TwT。滚粗真的很残酷啊，说走就走，有时根本来不及反应QwQ