当前位置：首页 > 洛谷 > 洛谷P4551题解题报告：图论与Trie树优化异或路径问题的实战解析

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

1天前

一、题目解读

洛谷P4551题要求在一个无向图中，寻找任意两点路径权值异或后的最大值。题目输入为图的边信息（点数n和n-1条边），每条边包含起点、终点及权值。需输出所有路径中权值异或的最大值。问题核心在于高效计算任意两点路径的异或和，并找到最大值。

二、解题思路

采用“预处理+Trie树查询”策略：

1. DFS预处理：通过深度优先搜索（DFS）遍历图，计算每个节点到根节点（默认为1）的路径权值异或和，存储于d数组。

2. Trie树优化：将d数组中的每个值插入Trie树（二进制字典树），查询时利用Trie树特性，优先选择与当前位相反的子节点，以最大化异或结果。

3. 贪心思想：每次查询时，从高位到低位遍历，若存在相反位分支，则选择该分支，确保异或值尽可能大。

三、解题步骤

1. 建图：使用邻接表存储无向图，边信息包含终点和权值。

2. 预处理异或路径：从根节点开始DFS，递归计算每个节点到根的异或值d[i] = d[父节点] ^ 边权值。

3. 构建Trie树：将d数组元素逐位插入Trie树，每个节点维护0/1子节点指针。

4. 查询最大值：对每个d[i]，在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;
}