题目链接：BZOJ 2115

考虑一个包含 $n$ 个点和 $m$ 条边的无向连通图，节点编号为 $1$ 到 $n$，第 $i$ 条边的边权为非负整数 $D_{i}$。试求出一条从 $1$ 号节点到 $n$ 号节点的路径，使得路径上经过的边的全是的 $\text{XOR}$ 和最大。

路径可以重复经过某些点或边，当一条边在路径中出现了多次时，其权值在计算 $\text{XOR}$ 和时也要被计算相应多的次数。

数据范围：$1 \le n \le 5 \times 10 ^ {4}$，$1 \le m \le 10 ^ {5}$，$0 \le D_{i} \le 10 ^ {18}$。

Solution

震惊！WC 竟出裸题！

我们从起点求出每个点的任何一条路径的 $\text{XOR}$ 值。如果存在边 $(u, v, w)$ 且 $v$ 的 $\text{DFS}$ 序小于 $u$（即在访问 $u$ 之前已经访问过 $v$ 了），那么可以知道这个环的 $\text{XOR}$ 值为 $dis_{u} \oplus dis_{v} \oplus w$。

由于任何一个环都可以改变答案，所以我们把环的值插入到线性基里，最后使用 $dis_{n}$ 更新答案即可。

时间复杂度：$\mathcal O(n + m \log w)$，其中 $w$ 为 $D_{i}$ 的值域。

Code

#include <cstdio>
#include <algorithm>

const int N = 5e4 + 5, M = 2e5 + 5;

int n, m, tot, lnk[N], ter[M], nxt[M];
long long val[M], dis[N];

struct LinearBase {
    static const int N = 63;

    long long r[N];

    void insert(long long v) {
        for (int i = 62; i >= 0; i--) {
            if (((v >> i) & 1) == 1) {
                if (r[i] == 0) {
                    r[i] = v;
                    break;
                } else {
                    v ^= r[i];
                }
            }
        }
    }
    long long query(long long ans) {
        for (int i = 62; i >= 0; i--) {
            if ((ans ^ r[i]) > ans) ans ^= r[i];
        }
        return ans;
    }
} base;

void addEdge(int u, int v, long long w) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, val[tot] = w;
}
void dfs(int u) {
    for (int i = lnk[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (dis[v] < 0) {
            dis[v] = dis[u] ^ val[i];
            dfs(v);
        } else {
            base.insert(dis[u] ^ dis[v] ^ val[i]);
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; i++) {
        long long w;
        scanf("%d%d%lld", &u, &v, &w);
        addEdge(u, v, w), addEdge(v, u, w);
    }
    std::fill(dis + 1, dis + n + 1, -1);
    dis[1] = 0;
    dfs(1);
    printf("%lld\n", base.query(dis[n]));
    return 0;
}