最长异或路径
题目描述
给定一棵 \(n\) 个点的带权树，结点下标从 \(1\) 开始到 \(n\)。寻找树中找两个结点，求最长的异或路径。
异或路径指的是指两个结点之间唯一路径上的所有边权的异或。
输入格式
第一行一个整数 \(n\)，表示点数。
接下来 \(n-1\) 行，给出 \(u,v,w\) ，分别表示树上的 \(u\) 点和 \(v\) 点有连边，边的权值是 \(w\)。
输出格式
一行，一个整数表示答案。
样例 #1
样例输入 #1
4
1 2 3
2 3 4
2 4 6
样例输出 #1
7
提示
最长异或序列是 \(1,2,3\)，答案是 \(7=3\oplus 4\)。
数据范围
\(1\le n \le 100000;0 < u,v \le n;0 \le w < 2^{31}\)。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
int head[5211314], nex[5211314], to[5211314], val[5211314], cnt;
int sum[5211314], bit[5211314];
bool opt[5211314];
inline void AddPoi(int v1, int v2, int w) {
++ cnt;
nex[cnt] = head[v1];
head[v1] = cnt;
to[cnt] = v2;
val[cnt] = w;
return;
}
struct Trie {
int trie[5211314][2], tot = 1;
inline void Insert(int a) {
int p = 1;
for (int i = 31; i >= 0; -- i) {
bool flag = (bit[i] & a);
if (trie[p][flag] == 0) {
trie[p][flag] = ++ tot;
}
p = trie[p][flag];
//正常01trie
}
}
inline int Query() {
int ans = 0;
for (int i = 2; i <= n; ++ i) {
int p = 1, now = 0;
for (int j = 31; j >= 0; -- j) {
bool flag = !(bit[j] & sum[i]);
if (trie[p][flag] != 0) {
p = trie[p][flag];
now += flag;
}//贪心，有不同于sum[i]的方向的就走不同于sum[i]的方向
else {
flag = !flag;
p = trie[p][flag];
now += flag;
}
if (j != 0) now <<= 1;
//注意特判
}
ans = max(ans, sum[i] ^ now);
//更新
}
return ans;
}
}tree;
void PreTreatment(int now, int num) {
sum[now] = num;
opt[now] = true;
for (int i = head[now]; i != 0; i = nex[i]) {
if (opt[to[i]] == false) {
if (now == 0) PreTreatment(to[i], val[i]);
else PreTreatment(to[i], num ^ val[i]);
//预处理好根节点到每一个节点路径上的异或值
}
}
return;
}
int main() {
bit[0] = 1;
for (int i = 1; i <= 31; ++ i) {
bit[i] = bit[i - 1] << 1;
//将1的每一位储存
}
cin >> n;
for (int i = 1, u, v, w; i <= n - 1; ++ i) {
cin >> u >> v >> w;
AddPoi(u, v, w);
AddPoi(v, u, w);
//连双向边
}
sum[1] = 0;//1到1是0
PreTreatment(1, 0);
for (int i = 1; i <= n; ++ i) {
//将sum[1]插入的原因是也要把从根节点到别的点的路径算上
//不插入1的话就不能将根节点作为端点
tree.Insert(sum[i]);
}
cout << tree.Query() << endl;
return 0;
}