算法
(dfs序 + 树状数组) $O(nlogn)$
#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define ios ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
void print() { cout << '\n'; }
template <typename T, typename...Args>
void print(T t, Args...args) { cout << t << ' '; print(args...); }
using P = pair<int, int>;
using ll = long long;
const int N = 200010;
// function
template <typename T> void chmax(T &x, T y) { x = max(x, y); }
template <typename T> void chmin(T &x, T y) { x = min(x, y); }
template <typename T = int>
vector<T> readVector(int n) {
vector<T> a(n);
for(T &x: a) cin >> x;
return a;
}
vector<vector<int>> readGraphWithoutWeight(int n, int m, bool isDirected = false) {
vector<vector<int>> g(n);
while(m --) {
int u, v;
cin >> u >> v;
u --;
v --;
g[u].pb(v);
if(!isDirected) g[v].pb(u);
}
return g;
}
template <typename U = int>
struct BIT {
int n;
vector<U> tr;
BIT () {}
BIT (int _n): n(_n), tr(_n + 1) {}
void mdf(int x, U p) {
for(int i = x; i <= n; i += i & -i) {
tr[i] ^= p;
}
}
U pre(U x) {
U res = 0;
for(int i = x; i; i -= i & -i) {
res ^= tr[i];
}
return res;
}
U qry(int l, int r) {
return pre(r) ^ pre(l - 1);
}
};
void solve(){
int n, m;
cin >> n >> m;
auto a = readVector(n);
auto e = readGraphWithoutWeight(n, n - 1);
vector<int> l(n), r(n);
int tot = 0;
function<void(int, int)> dfs = [&](int u, int fa) {
l[u] = ++ tot;
for(int v: e[u]) {
if(v == fa) continue;
dfs(v, u);
}
r[u] = tot;
};
dfs(0, -1);
BIT t(n);
for (int i = 0; i < n; i ++) {
t.mdf(l[i], a[i]);
}
while (m --) {
int op, x;
cin >> op >> x;
x --;
if (op == 1) {
int y;
cin >> y;
t.mdf(l[x], a[x]);
a[x] = y;
t.mdf(l[x], y);
} else {
print(t.qry(l[x], r[x]));
}
}
}
int main() {
ios
int t = 1; //cin >> t;
while(t --) solve();
return 0;
}