01字典树
2025-10-19 18:03:33
发布于：北京
6阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
struct node {
int v, w;
};
int n;
int u, v, w;
vector<node> s[100005];
int zs[100005];
void dfs(int x, int fa) {
for (int i = 0; i < s[x].size(); i++){
int y = s[x][i].v;
if (y != fa) {
zs[y] = zs[x] ^ s[x][i].w;
dfs(y, x);
}
}
}
struct trie {
int ne[2];
int val;
} st[5000005];
int l;
void add(long long x) {
int root = 0;
for (int i = 31; i >= 0; i--) {
int k = (x >> i) & 1;
if (st[root].ne[k] == 0) {
st[root].ne[k] = ++l;
}
root = st[root].ne[k];
}
st[root].val = x;
}
long long find(long long x) {
int root = 0;
for (int i = 31; i >= 0; i--) {
int k = x >> i & 1;
if (st[root].ne[k ^ 1]) {
root = st[root].ne[k ^ 1];
} else {
root = st[root].ne[k];
}
}
return st[root].val;
}
int main() {
cin >> n;
for (int i = 1; i < n; i++) {
cin >> u >> v >> w;
s[u].push_back({v, w});
s[v].push_back({u, w});
}
dfs(1, 0);
for (int i = 1; i <= n; i++) {
add(zs[i]);
}
long long maxx = 0;
for (int i = 1; i <= n; i++) {
maxx = max(find(zs[i])^zs[i], maxx);
}
cout << maxx;
return 0;
}
这里空空如也
有帮助，赞一个