洛谷P4551题解题报告：图论与Trie树优化异或路径问题的实...

19339201706 · 发表于前天 15:29

一、题目解读

洛谷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[MAXN]; // 邻接表

int trie[MAXN * BIT][2], cnt = 1; // Trie树，cnt为节点计数器

int d[MAXN]; // 节点到根的异或路径值

// 预处理异或路径（DFS）

void dfs(int u, int fa) {

for (auto &e : G[u]) { // 遍历u的所有邻接边

      if (e.to == fa) continue; // 跳过父节点

      d[e.to] = d[u] ^ 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[p][b]) trie[p][b] = ++cnt; // 若子节点不存在，创建新节点

      p = trie[p][b]; // 移动到子节点

}

}

// 查询与x异或最大的值

int query(int x) {

int p = 1, res = 0; // 从根节点开始，结果初始化

for (int i = BIT; i >= 0; i--) {

      int b = (x >> i) & 1; // 当前位

      if (trie[p][!b]) { // 若相反位分支存在

         res += (1 << i); // 累加贡献值

         p = trie[p][!b]; // 转向相反分支

      } else {

         p = trie[p][b]; // 否则沿原分支

      }

}

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[u].push_back({v, w}); // 双向建边

      G[v].push_back({u, w});

}

dfs(1, 0); // 从根节点1开始预处理

int ans = 0;

for (int i = 1; i <= n; i++) {

      insert(d[i]); // 插入到Trie树

      ans = max(ans, query(d[i])); // 更新最大异或值

}

cout << ans << endl; // 输出结果

return 0;

}
复制代码

五、总结
本解法巧妙结合图论预处理与Trie树查询，将路径异或问题转化为二进制位匹配问题。通过预处理计算节点到根的异或值，利用Trie树高效查找最大异或值，时间复杂度为O(nlogn)。该算法对处理大规模异或路径问题具有借鉴意义，尤其适用于需要快速查找异或极值的场景。
来源：自学信奥