自动搬运

查看原文

来自洛谷，原作者为

	LS_Z_66066 秋殇别恋

搬运于2025-08-24 23:15:08，当前版本为作者最后更新于2025-05-02 21:15:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道树状数组结合 dfs 序的简单应用。

题目要求点修区间查，考虑树状数组。

首先求出每个节点的 dfs 序，按照深搜的性质可得同一子树内的 dfs 序一定是连续的一段，即可把题目从树上问题转换成序列问题，之后就是单点修改和查询区间异或和。

Code：

#include <bits/stdc++.h>//
//#define Ri register int
//#define int long long
#define eb emplace_back
#define pb push_back

typedef long long ll;

inline int read(){
	int x = 0; bool f = 1;
	char ch = getchar();
	while(ch < 48 || ch > 57){
		if(ch == 45) f = 0;
		ch = getchar();
	}
	while(ch <= 57 && ch >= 48){
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return f ? x : -x;
}

const int N = 1e5 + 3;

int n, m;

int a[N];

int dfn[N], tot, siz[N];

std :: vector<int> e[N];

inline void dfs(int u, int fath = 0) {
	dfn[u] = ++tot;
	siz[u] = 1;
	for(auto &v : e[u]) if(v ^ fath) {
		dfs(v, u);
		siz[u] += siz[v];
	}
}

int c[N];

inline void add(int x, int k) {
	for(; x <= n; x += (x & -x)) c[x] ^= k;
}

inline int qry(int x, int res = 0) {
	for(; x >= 1; x -= (x & -x)) res ^= c[x];
	return res;
}

signed main(){
	n = read(), m = read();
	for(int i = 1; i <= n; ++i) a[i] = read();
	
	int op, x, y;
	for(int i = 1; i < n; ++i) x = read(), y = read(), e[x].eb(y), e[y].eb(x);
	
	dfs(1);
	
	for(int i = 1; i <= n; ++i) add(dfn[i], a[i]);
	
	while(m--) {
		op = read(), x = read();
		if(op & 1) {
			y = read();
			add(dfn[x], a[x]);
			add(dfn[x], a[x] = y);
		}
		else {
			std :: cout << (qry(dfn[x] + siz[x] - 1) ^ qry(dfn[x] - 1)) << "\n";
		}
	}

	return 0;
}

已更正格式。