洛谷P4551题解题报告：图论与Trie树优化异或路径问题的实...
https://www.xinaozhilu.cn/zb_users/upload/2025/06/202506091749398636689645.jpg一、题目解读洛谷P4551题要求在一个无向图中，寻找任意两点路径权值异或后的最大值。题目输入为图的边信息（点数n和n-1条边），每条边包含起点、终点及权值。需输出所有路径中权值异或的最大值。问题核心在于高效计算任意两点路径的异或和，并找到最大值。二、解题思路采用“预处理+Trie树查询”策略： 1. DFS预处理：通过深度优先搜索（DFS）遍历图，计算每个节点到根节点（默认为1）的路径权值异或和，存储于d数组。 2. Trie树优化：将d数组中的每个值插入Trie树（二进制字典树），查询时利用Trie树特性，优先选择与当前位相反的子节点，以最大化异或结果。 3. 贪心思想：每次查询时，从高位到低位遍历，若存在相反位分支，则选择该分支，确保异或值尽可能大。三、解题步骤1. 建图：使用邻接表存储无向图，边信息包含终点和权值。2. 预处理异或路径：从根节点开始DFS，递归计算每个节点到根的异或值d = d[父节点] ^ 边权值。3. 构建Trie树：将d数组元素逐位插入Trie树，每个节点维护0/1子节点指针。4. 查询最大值：对每个d，在Trie树中从高位到低位遍历，若当前位相反分支存在，则转向该分支，累加贡献值，最终得到最大异或值。5. 更新答案：遍历所有节点的查询结果，取最大值输出。四、代码与注释#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5; // 最大点数
const int BIT = 30; // 二进制位数
// 边结构
struct Edge {
int to, w;
};
vector<Edge> G; // 邻接表
int trie, cnt = 1; // Trie树，cnt为节点计数器
int d; // 节点到根的异或路径值
// 预处理异或路径（DFS）
void dfs(int u, int fa) {
for (auto &e : G) { // 遍历u的所有邻接边
if (e.to == fa) continue; // 跳过父节点
d = d ^ e.w; // 更新子节点的异或值
dfs(e.to, u); // 递归处理子树
}
}
// 向Trie树插入数字x
void insert(int x) {
int p = 1; // 从根节点开始
for (int i = BIT; i >= 0; i--) { // 从最高位到最低位
int b = (x >> i) & 1; // 获取当前位
if (!trie) trie = ++cnt; // 若子节点不存在，创建新节点
p = trie; // 移动到子节点
}
}
// 查询与x异或最大的值
int query(int x) {
int p = 1, res = 0; // 从根节点开始，结果初始化
for (int i = BIT; i >= 0; i--) {
int b = (x >> i) & 1; // 当前位
if (trie[!b]) { // 若相反位分支存在
res += (1 << i); // 累加贡献值
p = trie[!b]; // 转向相反分支
} else {
p = trie; // 否则沿原分支
}
}
return res;
}
int main() {
int n;
cin >> n; // 输入点数
for (int i = 1; i < n; i++) { // 输入n-1条边
int u, v, w;
cin >> u >> v >> w;
G.push_back({v, w}); // 双向建边
G.push_back({u, w});
}
dfs(1, 0); // 从根节点1开始预处理
int ans = 0;
for (int i = 1; i <= n; i++) {
insert(d); // 插入到Trie树
ans = max(ans, query(d)); // 更新最大异或值
}
cout << ans << endl; // 输出结果
return 0;
}
五、总结本解法巧妙结合图论预处理与Trie树查询，将路径异或问题转化为二进制位匹配问题。通过预处理计算节点到根的异或值，利用Trie树高效查找最大异或值，时间复杂度为O(nlogn)。该算法对处理大规模异或路径问题具有借鉴意义，尤其适用于需要快速查找异或极值的场景。来源：自学信奥
页:
[1]