Cow Land

问题复述：树上单点更新，求两点 $a$ , $b$ 间路径上每个点的值的XOR。

如果直观来做这个题，就是每个查询从 $a$ 到 $b$ 走一遍（要找最短路，可以从是根出发分别走到 $a$ 和 $b$ ，然后在分叉处连起来），但这样肯定会TLE。我们需要 $\mathcal{O}(n \log n)$ 的算法。

首先考虑没有更新的情况，容易想到可以通过一遍DFS，算出从根到每个节点s的路径的XOR，记为 $X_s$ 。这时 $a$ , $b$ 路径的XOR，应该就是 $X_a \oplus X_b \oplus \tt{LCA}(a, b)$ 。注意：两条路径异或的时候， LCA这个点也会被抵消掉，而最终结果需要这个点，所以需要再XOR上去。

LCA的求解是一个现成的问题，通常用倍增来解决，在下面的程序中，作为不同解法的示例，我们用欧拉回路来解决。

再考虑加入点的更新怎么办。每次更新一个点 $u$ 的时候，对于 $X$ 来说，就是要更新 $u$ 的子树中所有点 $v$ 的 $X_v$ ，这个问题放到树的遍历数组上来考虑，因为每棵子树对应DFN遍历数组上连续的区间，所以问题可以转化成数组上的区间更新，点查询问题。所以我们对问题的完整解法，就是在DFS遍历树上，用线段树的区间更新，点查询（range update point query）来求（标准方法，存储差分值）。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, Q; 
int e[100005];
vector<int> adj[100005];
int st[100005], en[100005];     // [st, en) 
 
int tree[200005];
 
void update(int k, int x) {
    k += n;
    tree[k] ^= x;
    for (k /= 2; k >= 1; k /= 2) {
        tree[k] = tree[2*k] ^ tree[2*k+1];
    }
}
 
int exor(int a, int b) {
    a += n; b += n;
    int s = 0;
    while (a <= b) {
        if (a%2 == 1) s ^= tree[a++];
        if (b%2 == 0) s ^= tree[b--];
        a /= 2; b /= 2;
    }
    return s;
}
 
// build range update point query tree
int ti;
void dfs(int s, int p) {
    update(ti, e[s]);
    st[s] = ti++;
    for (int u: adj[s]) {
        if (u == p) continue;
        dfs(u, s);
    }
    en[s] = ti;
    if (ti < n) update(ti, e[s]);
}
 
// LCA through euler tour
struct LCA {
    vector<int> height, euler, first, segtree;
    vector<bool> visited;
 
    LCA(vector<int> adj[], int root = 0) {
        height.resize(n);
        first.resize(n);
        euler.reserve(n * 2);
        visited.assign(n, false);
        dfs(adj, root);
        int m = euler.size();
        segtree.resize(m * 4);
        build(1, 0, m - 1);
    }
 
    void dfs(vector<int> adj[], int node, int h = 0) {
        visited[node] = true;
        height[node] = h;
        first[node] = euler.size();
        euler.push_back(node);
        for (auto to : adj[node]) {
            if (!visited[to]) {
                dfs(adj, to, h + 1);
                euler.push_back(node);
            }
        }
    }
 
    void build(int node, int b, int e) {
        if (b == e) {
            segtree[node] = euler[b];
        } else {
            int mid = (b + e) / 2;
            build(node << 1, b, mid);
            build(node << 1 | 1, mid + 1, e);
            int l = segtree[node << 1], r = segtree[node << 1 | 1];
            segtree[node] = (height[l] < height[r]) ? l : r;
        }
    }
 
    int query(int node, int b, int e, int L, int R) {
        if (b > R || e < L)
            return -1;
        if (b >= L && e <= R)
            return segtree[node];
        int mid = (b + e) >> 1;
 
        int left = query(node << 1, b, mid, L, R);
        int right = query(node << 1 | 1, mid + 1, e, L, R);
        if (left == -1) return right;
        if (right == -1) return left;
        return height[left] < height[right] ? left : right;
    }
 
    int lca(int u, int v) {
        int left = first[u], right = first[v];
        if (left > right)
            swap(left, right);
        return query(1, 0, euler.size() - 1, left, right);
    }
};
 
int main() {
    scanf("%d %d", &n, &Q);
    for (int i = 0; i < n; i++)
        scanf("%d", &e[i]);
    for (int i = 0; i < n-1; i++) {
        int u,v;
        scanf("%d %d", &u, &v);
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(0,-1);
    LCA lca(adj);
    for (int q = 0; q < Q; q++) {
        int c, a, b;
        scanf("%d %d %d", &c, &a, &b);
        a--;
        if (c == 1) {
            int d = e[a] ^ b;
            update(st[a], d);
            if (en[a] < n) update(en[a], d);
            e[a] = b;
        } else {
            b--;
            // query XOR of [a,b]
            int l = e[lca.lca(a,b)];
            printf("%d\n", l ^ exor(0,st[a]) ^ exor(0,st[b]));
        }
    }
    return 0;
}