记录
13:56 2024-2-10
找到俩个点，获得最大的边权异或值。利用异或的性质，一个值被异或俩次相当于没有异或即 a xor b xor b = a
所以先从顶点出发，获得每个点路径上的异或值，然后对这俩个值进行异或就获得了他们之间路径的异或值。
获取从顶点到每个点路径上的异或值后，可以利用trie来找到最大的值，将值看成二进制数建立Trie
利用异或的特性每次找相反的路径，从而找到与当前值异或得到最大值的值。
点击查看代码
#include<iostream>
#include<vector>
#include<stdio.h>
#include<string.h>
using namespace std;
const int MAXN = 100010;
typedef unsigned long long ull;
typedef unsigned long ul;
int head[MAXN], ver[MAXN * 2], edge[MAXN * 2], Next[MAXN * 2], visit[MAXN], tot;
// 根节点到x路径上所有边权的xor值
// value[x] = value[fa[x]] xor tree[fa[x]][x]
int value[MAXN];
int N;
void add(int x, int y, int z) {
ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
}
void dfs(int x, int fa, int weight) {
visit[x] = 1;
if(fa != -1 && weight != -1) {
value[x] = value[fa] ^ weight;
}
for(int i = head[x]; i; i = Next[i]) {
int y = ver[i];
if(visit[y] == 0) {
// y是x的子节点
dfs(y, x, edge[i]);
}
}
}
void dfs(int x) {
visit[x] = 1;
for(int i = head[x]; i; i = Next[i]) {
int y = ver[i];
if(visit[y] == 0) {
value[y] = value[x] ^ edge[i];
// y是x的子节点
dfs(y, x, edge[i]);
}
}
}
int trie[MAXN * 32][2], ind = 1, val[MAXN * 32];
void insert(int x) {
int p = 1;
for(int k = 31; k >= 0; k--) {
// 获取x的第k位
int v = (x >> k) & 1;
if(!trie[p][v]) trie[p][v] = ++ind;
p = trie[p][v];
}
val[p] = x;
}
int get(int x) {
int p = 1;
for(int k = 31; k >= 0; k--) {
int v = (x >> k) & 1;
// 为了获取 xor的最大值 需要走另一个方向 即 v xor 1
if(trie[p][v ^ 1]) p = trie[p][v ^ 1];
else p = trie[p][v];
}
return val[p];
}
int main() {
while (cin >> N) {
memset(head, 0, sizeof(head));
memset(ver, 0, sizeof(ver));
memset(Next, 0, sizeof(Next));
memset(edge, 0, sizeof(edge));
memset(visit, 0, sizeof(visit));
memset(value, 0, sizeof(value));
tot = 0;
memset(trie, 0, sizeof(trie));
memset(val, 0, sizeof(val));
ind = 1;
int u, v, w;
for(int i = 0; i < N - 1; i++) {
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
dfs(0);
// dfs(0, -1, -1) 另一种写法 太繁琐了
int result = 0;
// 利用 trie树求最大异或值
// The XOR Largest Pair
for(int i = 0; i < N; i++) {
result = max(result, value[i] ^ get(value[i]));
insert(value[i]);
}
cout << result << endl;
}
}