P4151 [WC2011] 最大XOR和路径

这道题的关键在于对路径的处理。

我们先考虑如果给定的图是树的特殊情况。这种情况下， $1\to n$ 的最大异或和必定是 $1\to n$ 的简单路径，因为如果走分支，那么分支上边一定会走两次（沿着边往下走，沿着边走回来），其值异或两次后抵消。

然后我们给树加上一些非树边。比如说考虑

2 4 是非树边，我们想求 $1\to 5$ 的最大异或和路径。不同于 $1\to 3\to 5$ ，我们这次可以选择先绕 $1\to 3\to 4\to 2\to 1\to 3$ 走一圈，再走到 $5$ . 这条路径的异或和就是 $1\to 5$ 的树上简单路径加上 $1,2,3,4$ 这个环的异或值。

所以，类似的，我们对原图求出一棵 DFS 树，对于非树边 $(u,v)$ ，记下环 $(u,v,LCA(u,v))$ 上的异或和 $C_{u,v}$ ；同时找出 $1\to n$ 的树上简单路径的异或和 $P$ 。我们的答案，一定就是 $P,C_{i,j}$ 异或出来的最大值（其中 $P$ 是必选的）。我们对 $C_{i,j}$ 构造线性基，用贪心法找最大值即可。

Code

#include <iostream>
#include <tuple>
#include <vector>
constexpr int N = 5e4 + 5;
constexpr int M = 1e5 + 5;
constexpr int B = 63;
using i64       = long long;
using pil       = std::tuple<int, i64>;
using pii       = std::tuple<int, int>;
using edge      = std::tuple<int, i64>;
using vpil      = std::vector<pil>;
using vi        = std::vector<int>;

int n, m;
vi G[N], T[N];
edge E[M];
int on_tree[M], vis[N];
std::vector<i64> basis;
i64 sinceRoot[N];

void tree(int u, int fa) {
    vis[u] = true;
    for (auto eid : G[u]) {
        auto [uv, w] = E[eid];
        int v        = uv ^ u;
        if (v == fa)
            continue;
        if (vis[v]) {
            basis.push_back(w ^ sinceRoot[u] ^ sinceRoot[v]);
            continue;
        }
        sinceRoot[v] = sinceRoot[u] ^ w;
        on_tree[eid] = 1;
        T[u].push_back(eid);
        T[v].push_back(eid);
        tree(v, u);
    }
}

int main() {
    // std::cin.tie(0)->sync_with_stdio(0);
    std::cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        i64 w;
        std::cin >> u >> v >> w;
        E[i] = {u ^ v, w};
        G[u].emplace_back(i), G[v].emplace_back(i);
    }

    tree(1, 0);

    // linear basis
    int row       = 0;
    int len       = basis.size();
    auto checkbit = [&](i64 x, int b) { return (x >> b) & 1; };
    for (int col = B; col >= 0 && row < len; col--) {
        for (int to = row; to < len; to++) {
            if (checkbit(basis[to], col)) {
                std::swap(basis[to], basis[row]);
                break;
            }
        }

        if (not checkbit(basis[row], col))
            continue;
        for (int i = 0; i < len; i++) {
            if (i == row)
                continue;
            if (checkbit(basis[i], col))
                basis[i] ^= basis[row];
        }
        row++;
    }

    i64 ans = sinceRoot[n];
    for (int i = 0; i < row; i++)
        if ((ans ^ basis[i]) > ans)
            ans ^= basis[i];
    std::cout << ans << '\n';
}