当前位置：首页 > 洛谷 > 洛谷P2420题解析：树结构异或路径的高效求解算法

洛谷P2420题解析：树结构异或路径的高效求解算法

6小时前

一、题目解读

洛谷P2420题要求处理一棵树上的路径异或问题。给定一棵包含N个节点的树，每条边有权值，需回答M次查询：求节点u到节点v路径上所有边权值的异或和。题目关键在于如何高效利用树结构和异或运算的性质，避免重复计算，从而在O(N+M)时间内完成预处理和查询。

二、解题思路

核心思想是通过一次深度优先搜索（DFS）预处理每个节点到根节点的异或值，并存储于xor_val数组。由于路径异或值可分解为起点到根与终点到根的异或差，查询时直接异或两节点值即可。关键在于利用异或的“自逆性”（A^B^B = A）简化路径计算，避免遍历边。

三、解题步骤

1. 建树：通过输入构建邻接表存储树结构，每条边双向存储。

2. 预处理：从根节点1开始DFS，递归计算每个节点的xor_val，更新方式为当前路径异或值^边权值。

3. 查询处理：每次查询(u,v)，直接输出xor_val[u] ^ xor_val[v]，即为路径异或和。

四、代码与注释

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1e5 + 5; // 最大节点数

struct Edge {
    int to, w; // 边指向的节点和权值
};

vector<Edge> tree[MAXN]; // 邻接表存储树结构
int xor_val[MAXN]; // 节点到根节点的异或值
bool visited[MAXN]; // 标记节点是否访问

// DFS预处理每个节点的异或值
void dfs(int u, int current_xor) {
    visited[u] = true; // 标记访问
    xor_val[u] = current_xor; // 更新当前节点值
    
    for (const Edge& e : tree[u]) { // 遍历邻接边
        if (!visited[e.to]) { // 未访问的子节点递归
            dfs(e.to, current_xor ^ e.w); // 传递异或值：当前值^边权
        }
    }
}

int main() {
    ios::sync_with_stdio(false); // 加快IO
    cin.tie(nullptr);
    
    int N; cin >> N; // 节点数
    for (int i = 1; i < N; ++i) { // 构建树
        int u, v, w; cin >> u >> v >> w;
        tree[u].push_back({v, w}); // 双向边
        tree[v].push_back({u, w});
    }
    
    dfs(1, 0); // 从根节点开始预处理，初始异或为0
    
    int M; cin >> M; // 查询次数
    while (M--) {
        int u, v; cin >> u >> v;
        cout << (xor_val[u] ^ xor_val[v]) << '\n'; // 直接异或输出结果
    }
    return 0;
}