题目描述
给定一个树,树上的边都具有权值。
树中一条路径的异或长度被定义为路径上所有边的权值的异或和:
⊕ 为异或符号。
给定上述的具有n个节点的树,你能找到异或长度最大的路径吗?
样例
输入样例:
4
0 1 3
1 2 4
1 3 6
输出样例:
7
算法1
(Trie树)
1.首先对输入的子节点与父节点 建立邻接表(无向图)。
2.搜索无向图,计算每个节点到root节点的权值(dfs),即可得到如上题中的权值$a[i]$
3.与上题一样 搜索Trie树即可。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = 200010;
int son[3100010][2], n, a[N], idx;
int h[N], e[M], c[M], ne[M], cnt;
void add(int u, int v, int w){
e[cnt] = v, c[cnt] = w, ne[cnt] = h[u], h[u] = cnt ++;
}
void dfs(int u, int father, int sum){
a[u] = sum;
for (int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if (j != father) dfs(j, u, sum ^ c[i]);
}
}
void insert(int x){
int p = 0;
for (int i = 30; i >= 0; i --){
int s = x >> i & 1;
if (!son[p][s]) son[p][s] = ++ idx;
p = son[p][s];
}
}
int search(int x){
int p = 0, res = 0;
for (int i = 30; i >= 0; i --){
int s = x >> i & 1;
if (son[p][!s]){
res += 1 << i;
p = son[p][!s];
}else{
p = son[p][s];
}
}
return res;
}
int main(){
memset(h, -1, sizeof h);
scanf("%d", &n);
for (int i = 0; i < n - 1; i ++){
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
dfs(0, -1, 0);
for (int i = 0; i < n; i ++) insert(a[i]);
int res = 0;
for (int i = 0; i < n; i ++){
res = max(res, search(a[i]));
}
cout << res << endl;
return 0;
}