洛谷 P2420 让我们异或吧

// P2420 让我们异或吧 —— 正解：**连 LCA 都不用**
//
// ★★★ 一句话：先一遍 BFS 求出「根到每个点的路径异或和」`d[u]`，那么
//
//       路径(u,v) 的异或和 = d[u] ^ d[v]
//
//   道理：`d[u] ^ d[v]` 里，**根到 LCA 那一段被算了两遍**，而 `x ^ x = 0` —— 自己抵消掉了。
//   ⇒ **不用求 LCA，不用建倍增表，查询是 O(1)。**
//
// ⚠⚠ 而这正是[第 52 章树上差分](/ch/52-tree-diff/)那条「上一章的正确写法就是这一章的 bug」
//   的反面：路径**和**是 `s[u] + s[v] − 2·s[lca]`（要减两遍），
//   路径**异或**是 `d[u] ^ d[v]`（**一遍都不用减**）。
//   ⇒ 照猫画虎写成 `d[u] ^ d[v] ^ d[lca]` 就把那一段又加了回去 —— 和 [P4551](/sol/p4551/) 同一个坑。
//
// ★ 这道题被放进[第 51 章](/ch/51-lca/)的题单，恰恰是为了让你先问一句：**这题到底要不要 LCA。**

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int head_[MAXN], nxt_[MAXN * 2], to_[MAXN * 2], wt_[MAXN * 2], ecnt;
int d[MAXN];
int n, m;

inline void addEdge(int u, int v, int w) { to_[++ecnt] = v; wt_[ecnt] = w; nxt_[ecnt] = head_[u]; head_[u] = ecnt; }

int main() {
    if (scanf("%d", &n) != 1) return 0;
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        if (scanf("%d %d %d", &u, &v, &w) != 3) return 0;
        addEdge(u, v, w);
        addEdge(v, u, w);                 // ⚠ 无向边，两边都要存
    }
    {                                     // BFS 一趟求 d（⚠ 别用递归，链有 10⁵ 层）
        vector<char> vis(n + 1, 0);
        vector<int> que;
        que.reserve(n);
        d[1] = 0; vis[1] = 1; que.push_back(1);
        for (size_t i = 0; i < que.size(); i++) {
            int u = que[i];
            for (int e = head_[u]; e; e = nxt_[e]) {
                int v = to_[e];
                if (vis[v]) continue;
                vis[v] = 1;
                d[v] = d[u] ^ wt_[e];
                que.push_back(v);
            }
        }
    }
    if (scanf("%d", &m) != 1) return 0;
    for (int i = 0; i < m; i++) {
        int u, v;
        if (scanf("%d %d", &u, &v) != 2) return 0;
        printf("%d\n", d[u] ^ d[v]);      // ★ u == v 时天然是 0，一个特判都不用写
    }
    return 0;
}