题解：P12385 [蓝桥杯 2023 省 Python B] 异或和

树状数组 + dfs 序

操作如此简单，信息如此单一，为何不进精简？

首先这个题并不需要完成链的操作，而只需要完成子树操作，所以只需要保存 两个信息即可，也就不需要完整的树剖，一遍深搜直接带走；

其次关于树状数组的单点覆盖，可以分成抵消原来的值以及加上当前的值，对于维护和的就是加减法，对于维护异或和的，就是对于两个值分别异或一下，之前的异或没了，现在的异或进去。

对于树转链的新手来说，注意进行修改、查询的时候一定一定一定代入的是 而不是 ！

#include<bits/stdc++.h>
#define lowbit(x) (x & (-x))

using namespace std;

const int MAXN = 100005;

int n, m;

int edgeCount;
int head[MAXN], toNode[MAXN << 1], nextEdge[MAXN << 1];

int countDfn, dfn[MAXN], siz[MAXN], val[MAXN];

int bit[MAXN];

inline void addEdge(int from, int to) {
    edgeCount++;
    toNode[edgeCount] = to;
    nextEdge[edgeCount] = head[from];
    head[from] = edgeCount;
    return;
}

inline void changeBit(int pos, int val) {
    for (int i = pos; i <= n; i += lowbit(i))
        bit[i] ^= val;
    return;
}
inline int queryBit(int l, int r) {
    int res1 = 0, res2 = 0;
    for (int i = l - 1; i; i -= lowbit(i))
        res1 ^= bit[i];
    for (int i = r; i; i -= lowbit(i))
        res2 ^= bit[i];
    return res1 ^ res2;
}

inline void dfs(int from, int father) {
    siz[from]++;
    countDfn++;
    dfn[from] = countDfn;
    for (int i = head[from]; i; i = nextEdge[i]) {
        int to = toNode[i];
        if (to != father) {
            dfs(to, from);
            siz[from] += siz[to];
        }
    }
    return;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &val[i]);
    for (int i = 1; i < n; ++i) {
        int from, to;
        scanf("%d%d", &from, &to);
        addEdge(from, to), addEdge(to, from);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; ++i)
        changeBit(dfn[i], val[i]);
    while (m--) {
        int opt, pos, curVal;
        scanf("%d%d", &opt, &pos);
        if (opt == 1) {
            scanf("%d", &curVal);
            changeBit(dfn[pos], val[pos]);
            changeBit(dfn[pos], curVal);
            val[pos] = curVal;
        } else
            cout << queryBit(dfn[pos], dfn[pos] + siz[pos] - 1) << '\n';
    }
    return 0;
}