dfs序列 + 树状数组
dfs序列维护入栈出栈时间戳,每个节点通过入栈出栈时间戳的范围可以找到对应子树所属时间戳范围,找子树的异或和等价于求这个区间范围的异或和,则问题转化为单点修改 + 区间查询,加之异或与加法性质相近,固可用树状数组维护。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10,M = 2 * N;
int n,m;//输入参数
int a[N][2],cnt; // a[i][0] 表示 入栈时间戳 a[i][1] 表示出栈时间戳
int tree[N]; // 树状数组
int v[N]; //各个结点的值
int lowbit(int x)
{
return x & -x;
}
void update(int x,int val){
int newv = val;
while(x <= N){
tree[x] ^= newv;
x += lowbit(x);
}
}
int query(int x){
int res = 0;
while(x > 0){
res ^= tree[x];
x -= lowbit(x);
}
return res;
}
// 邻接链表
int h[N], e[M], ne[M], idx;
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int root,int fa){ // 构建dfs序列
a[root][0] = ++cnt;
for(int i = h[root];~i;i = ne[i]){
int j = e[i];
if(fa == j) continue;
dfs(j,root);
}
a[root][1] = cnt;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
for(int i = 1;i <= n;i++){
cin >> v[i];
}
for(int i = 1;i < n;i++){
int u,v;
cin >> u >> v;
add(u, v);
add(v, u);
}
dfs(1,0); //构造dfs序
for(int i = 1;i <= n;i++) //初始化树状数组
update(a[i][0],v[i]);
for(int i = 1;i <= m;i++){
int op,x,y;
cin >> op;
if(op == 1){
cin >> x >> y;
int new_val = v[x] ^ y; //修改到另外一个值的异或,可以先异或自身,再异或修改的值
update(a[x][0], new_val);
v[x] = y;
}else{
cin >> x;
cout << (query(a[x][1]) ^ query(a[x][0] - 1)) << endl;
}
}
return 0;
}