题目描述
给定一棵 n 个点的带权树，结点下标从 1 开始到 n。寻找树中找两个结点，求最长的异或路径。
异或路径指的是指两个结点之间唯一路径上的所有边权的异或。
输入格式
第一行一个整数 n，表示点数。
接下来 n−1 行，给出 u,v,w ，分别表示树上的 u 点和 v 点有连边，边的权值是 w。
输出格式
一行，一个整数表示答案。
输入输出样例
输入 #1复制
4 1 2 3 2 3 4 2 4 6
输出 #1复制
7
说明/提示
最长异或序列是 1,2,3，答案是 7=3⊕4。
数据范围
1≤n≤100000;0<u,v≤n;0≤w<231。
代码实现：
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXBIT = 30;
// 树的邻接表表示
vector< pair<int, int> > adj[MAXN];
int xor_val[MAXN]; // 存储每个节点到根的异或和
// Trie树节点结构
struct TrieNode {
TrieNode* children[2];
TrieNode() {
children[0] = 0; // 使用0替代nullptr
children[1] = 0; // 兼容C++98/03
}
};
TrieNode* root;
// 插入数字到Trie树
void insert(int num) {
TrieNode* curr = root;
for (int i = MAXBIT; i >= 0; i--) {
int bit = (num >> i) & 1;
if (!curr->children[bit]) {
curr->children[bit] = new TrieNode();
}
curr = curr->children[bit];
}
}
// 查询与num异或的最大值
int query(int num) {
TrieNode* curr = root;
int res = 0;
for (int i = MAXBIT; i >= 0; i--) {
int bit = (num >> i) & 1;
int desired = 1 - bit;
if (curr->children[desired]) {
res |= (1 << i);
curr = curr->children[desired];
} else {
curr = curr->children[bit];
}
}
return res;
}
// DFS计算每个节点的异或和
void dfs(int u, int parent) {
for (int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i].first;
int w = adj[u][i].second;
if (v != parent) {
xor_val[v] = xor_val[u] ^ w;
dfs(v, u);
}
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n - 1; i++) {
int u, v, w;
cin >> u >> v >> w;
// 使用 push_back 和 make_pair 替代 emplace_back
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
// 计算每个节点的异或和
xor_val[1] = 0; // 根节点的异或和为0
dfs(1, -1);
// 构建Trie树并查询最大异或值
root = new TrieNode();
insert(xor_val[1]);
int max_xor = 0;
for (int i = 2; i <= n; i++) {
max_xor = max(max_xor, query(xor_val[i]));
insert(xor_val[i]);
}
cout << max_xor << endl;
return 0;
}