题目
分析
一个简单的例子
相信大家都做过这题：
Xor运算有一些很显然的性质：
\(a \oplus a = 0\)
\(a \oplus b = b \oplus a\)
\(a\oplus b\oplus c = a\oplus(b\oplus c)\)
对于这道水题，我们只需要随便取一个点作为根节点，预处理节点\(i\)到根节点的路径异或和\(dist[i]\)，然后\(a,b\)的路径的异或和即为\(dist[a]\oplus dist[b]\oplus dist[LCA(a,b)]\oplus dist[LCA(a,b)]=dist[a]\oplus dist[b]\)
回到本题
回到我们这题，我们只需要随便取一个点作为根节点，利用dfs处理出每个点到根节点的路径异或和，求这些异或和的最大异或即可，因为它们的LCA到根节点的路径被抵消了。
利用Trie实现求最大异或和。
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
struct edge {
int to, nxt, val;
} edges[MAXN << 1];
int head[MAXN], path[MAXN], trie[MAXN << 5][2], num = 2, tot = 0, cnt = 0, n;
bool vis[MAXN];
void addedge(int from, int to, int val) {
edges[cnt].to = to, edges[cnt].val = val, edges[cnt].nxt = head[from];
head[from] = cnt++;
}
void dfs(int x, int w) {
vis[x] = 1;
path[tot++] = w;
for(int i = head[x]; i != -1; i = edges[i].nxt) {
if(!vis[edges[i].to]) {
dfs(edges[i].to, w ^ edges[i].val);
}
}
}
void insert(int x) {
int cur = 1;
for(int i = 30; i >= 0; i--) {
int p = (x >> i) & 1;
if(trie[cur][p]) cur = trie[cur][p];
else cur = trie[cur][p] = num++;
}
}
int getmaxxor(int x) {
int cur = 1, ans = 0;
for(int i = 30; i >= 0; i--) {
int p = ((x >> i) & 1) ^ 1;
if(trie[cur][p]) {
cur = trie[cur][p];
ans = ans << 1 | 1;
} else {
cur = trie[cur][p ^ 1];
ans <<= 1;
}
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
memset(head, 0xff, sizeof(head));
int u, v, w;
cin >> n;
for(int i = 0; i < n - 1; i++) {
cin >> u >> v >> w;
addedge(u, v, w);
addedge(v, u, w);
}
dfs(1, 0);
int ans = 0;
for(int i = 0; i < n; i++) insert(path[i]);
for(int i = 0; i < n; i++) ans = max(ans, getmaxxor(path[i]));
cout << ans << endl;
return 0;
}