异或最长路（线性基应用）

首先异或最长路不能用 Bellman-Ford，因为异或不满足加法传递性，局部最优可能推不出整体最优，而且可能出现类似“负环”的情况，走不出来。一般要用线性基解决这一类问题。

我们可以把路径拆成一条链（蓝色）和若干个环（灰色）。我们可以走一条红色的路径到达一个环，转一圈然后原路返回，这样红色的边两次异或消掉了，我们白白获得了整个环的异或和。因为是连通图，我们可以用这样的方法获得图上所有的环的异或和，把这些异或和扔进一个集合，做子集异或和最大值，转化成了线性基的板子。

那么这个链要怎么取呢？发现我们可以随便取，因为如果有一条比这个蓝色链更好的绿色链，蓝色链和绿色链就构成了一个环。在做线性基的过程中，这个环被选入，就相当于把蓝色链异或两次消掉，留下了绿色链。这个过程是自动的，所以不需要单独考虑怎么取链。在 dfs 找环的时候会记录一个从 1 开始的路径异或和，直接使用就好了（见代码，P4151 [WC2011] 最大XOR和路径）。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

constexpr int N = 50000 + 10;
constexpr int M = 100000 + 10;

int n, m;
LL dis[N], p[61];
bool vis[N];
vector<pair<int, LL>> G[N];

void insert(LL x) { // 贪心法求线性基板子
    for (int i = 60; ~i; i--) {
        if (!(x >> i)) continue;
        if (!p[i]) {
            p[i] = x;
            break;
        }
        x ^= p[i];
    }
}

void dfs(int u, LL d) {
    dis[u] = d; // 记录一个从1开始的异或和
    vis[u] = 1;
    for (auto [v, w] : G[u]) {
        if (vis[v]) { // 找到环了
            insert(dis[u] ^ w ^ dis[v]); // 环的异或和=[1~u]^w^[1~v]，环外的部分异或没了
            continue;
        }
        dfs(v, dis[u] ^ w);
    }
}

int main() {
    cin.tie(0)->ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        LL w;
        cin >> u >> v >> w;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }
    dfs(1, 0);
    LL ans = dis[n]; // 直接用dfs出的[1~n]的异或和作为链长
    for (int i = 60; ~i; i--) {
        ans = max(ans, ans ^ p[i]);
    }
    cout << ans << '\n';
    return 0;
}