当前位置：首页 > news >正文

《P4551 最长异或路径》

news 来源：原创 2025/7/28 7:28:40

题目描述

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

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

输入格式

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

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

输出格式

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

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

最长异或序列是 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;
}