Luogu P4151 [WC2011] 最大XOR和路径 题解

Link

考虑我们在 01-Trie 上是怎么做的？是不是找到一段从根到 LCA 的东西相等然后处理不相等的后面部分？同理，我们对于这张图尝试用 DFS 处理出每个点的某一种路径答案，然后用线性基尝试代替求最优。

具体地，对于这个题我们两条路径如果在某个节点 \(x\) 相交，则在 \(x\) 记录两条路径的异或差 \(d\)。然后选择一条路径接着走，直到走到 \(n\)，记录当前答案为 \(g\)，比较 \(g, g \oplus d\) 的大小，较大者路径更优。

通过 DFS 在路径交点处处理出一堆异或差，记有 \(c\) 个这样的标签，则对这 \(2^c\) 个差值插入到线性基中，对 \(query\) 调用初值 \(g\) 求解。

#include <bits/stdc++.h>using i64 = long long;constexpr int N = 5e4 + 7;
constexpr int M = 2e5 + 7;int n, m, t;
int vis[N];
i64 xad[N];std::vector<std::pair<int, i64>> adj[N];struct LiB {i64 w[107];void insert(i64 x) {for (int i = 60; ~i; i--) {if (!(x & (1ll << i)))continue;if (!w[i]) { w[i] = x; return; }x ^= w[i];}}i64 query(i64 x) {i64 res = x;for (int i = 60; ~i; i--) {res = std::max(res, (res ^ w[i]));}return res;}
} li;void dfs(int u, i64 x) {vis[u] = 1; xad[u] = x;for (auto [v, w] : adj[u]) {if (!vis[v])dfs(v, x ^ w);elseli.insert(xad[v] ^ (x ^ w));}
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cin >> n >> m;for (int i = 1; i <= m; i++) {int u, v; i64 w;std::cin >> u >> v >> w;adj[u].push_back({v, w});adj[v].push_back({u, w});}dfs(1, 0);std::cout << li.query(xad[n]) << "\n";return 0;
}