洛谷P4551最长异或路径（01Trie）

题目描述

给定一棵nn个点的带权树，结点下标从11开始到NN。寻找树中找两个结点，求最长的异或路径。

异或路径指的是指两个结点之间唯一路径上的所有边权的异或。

输入格式

第一行一个整数NN，表示点数。

接下来 n−1n−1 行，给出 u,v,wu,v,w ，分别表示树上的 uu 点和 vv 点有连边，边的权值是 ww。

输出格式

一行，一个整数表示答案。

输入输出样例

输入 #1复制

4
1 2 3
2 3 4
2 4 6


输出 #1复制

7


先求出每个点到根的路径的异或和d[i]，两点之间的路径异或和就是d[x] ^ d[y]。把所有的d插入01trie求两个数异或最大值即可。

#include
using namespace std;
int trie[100005*31][2],tot=1,ans=0;
void insert(int x) {
int p = 1, k;
for(k = 31; k >= 0; k--) {
int ch = (x >> k) & 1;
if(trie[p][ch] == 0) trie[p][ch] = ++tot;
p = trie[p][ch];
}
}
int search(int x) {
int k, p = 1, ans = 0;
for(k = 31; k >= 0; k--) {
int now = (x >> k) & 1;
if(trie[p][now ^ 1]) {
ans = ans | (1 < p = trie[p][now ^ 1];
} else if(trie[p][now]) {
p = trie[p][now];
}
}
return ans;
}
int n, head[100005], ver[2 * 100005], Next[2 * 100005], edge[2 * 100005], tol;
void add(int x, int y, int z) {
ver[++tol] = y, edge[tol] = z, Next[tol] = head[x], head[x] = tol;
}
int d[100005];
void dfs(int x, int pre, int sum) {
for(int i = head[x]; i; i = Next[i]) {
int y = ver[i], z = edge[i];
d[y] = sum ^ z;
if(y == pre) continue;
dfs(y, x, sum ^ z);
}
}
int main() {
cin >> n;
for(int i = 1; i <= n - 1; i++) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
dfs(1, 0, 0);
for(int i = 1; i <= n; i++) {
insert(d[i]);
}
for(int i = 1; i <= n; i++) {
ans=max(ans,search(d[i]));
}
cout < return 0;
}