P2420让我们异或吧

代码由人类编写，文章由deepseek官网版本编写
博客食用更佳

题目解析：

本题要求我们在树结构中快速计算两个节点之间路径上所有边的异或值。由于树的结构特性，我们可以利用异或运算的性质来高效解决这个问题。

异或性质的应用：

异或运算具有以下重要性质：

自反性：a ^ a = 0
交换律和结合律：a ^ b = b ^ a，(a ^ b) ^ c = a ^ (b ^ c)
路径抵消性：树中两点间路径的异或值等于它们到根节点异或值的异或。

基于这些性质，我们可以将问题转化为预处理每个节点到根节点的异或值，然后通过简单的异或操作快速得到任意两节点路径的异或值。

解题思路：

预处理节点异或值：
- 选择一个根节点（例如节点1），进行深度优先搜索（DFS）或广度优先搜索（BFS）。
- 在遍历过程中，计算每个节点到根节点的异或值。对于当前节点 u 及其子节点 v，边权为 w，则 xor[v] = xor[u] ^ w。
处理查询：
- 对于每次查询的两个节点 u 和 v，直接输出 xor[u] ^ xor[v]。根据异或性质，这等价于路径 u 到 v 上所有边权的异或和。

代码实现：

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

const int MAXN = 100005;
vector<pair<int, int>> tree[MAXN]; // 邻接表存储树结构
int xorSum[MAXN]; // 存储每个节点到根的异或值

void dfs(int parent, int node, int currentXor) {
    xorSum[node] = currentXor;
    for (auto &[child, weight] : tree[node]) {
        if (child != parent) {
            dfs(node, child, currentXor ^ weight);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        tree[u].emplace_back(v, w);
        tree[v].emplace_back(u, w);
    }
    
    // 预处理异或值，根节点设为1
    dfs(0, 1, 0);
    
    int m;
    cin >> m;
    while (m--) {
        int u, v;
        cin >> u >> v;
        cout << (xorSum[u] ^ xorSum[v]) << '\n';
    }
    
    return 0;
}

代码解释：