洛谷P4551最长异或路径算法完全解析：从Trie树到DFS的完美结合

问题背景分析

洛谷P4551题目要求在一棵带权树中找出两个节点之间的路径，使得路径上所有边权的异或值最大。这是一个经典的树形结构问题，涉及图论、位运算和数据结构等多个知识点。

核心算法原理

1. 异或路径性质

• 任意两点u和v的路径异或值等于d[u]^d[v]，其中d[i]表示i节点到根的异或值

• 问题转化为在d数组中找出两个数使它们的异或值最大

2. Trie树优化

• 使用二进制Trie树高效存储所有d[i]值

• 通过贪心策略在Trie树上快速查询最大异或对

算法实现细节

1. DFS预处理：计算每个节点到根的异或值

2. Trie树构建：将所有d[i]插入到Trie树中

3. 最大查询：对每个d[i]在Trie树中查询其最大异或对

代码实现

#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;
int d[MAXN]; // 存储每个节点到根的异或值

// DFS预处理每个节点到根的异或值
void dfs(int u, int fa) {
    for (auto &e : G[u]) {
        if (e.to == fa) continue;
        d[e.to] = d[u] ^ e.w;
        dfs(e.to, u);
    }
}

// 插入数字到Trie树
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++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    
    dfs(1, 0); // 预处理异或路径
    
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        insert(d[i]);
        ans = max(ans, query(d[i]));
    }
    
    cout << ans << endl;
    return 0;
}

代码优化技巧

1. 使用静态数组代替动态分配

2. 预处理避免重复计算

3. 位运算优化