线段树+重链剖分

前置内容：线段树，重链剖分，请先学习对应内容再来阅读题解

#include<bits/stdc++.h>
using namespace std;
int n,q;
const int N = 1e5+10;
vector<int> g[N];
int e[N],dfn[N],rdfn[N],dep[N],fa[N],siz[N],wc[N],tot,top[N];
struct smt{
	int l,r;
	long long sum;
	#define l(p) t[p].l
	#define r(p) t[p].r
	#define sum(p) t[p].sum//区间异或和
}t[4*N];
void dfs1(int x,int f){
	dep[x]=dep[f]+1;
	fa[x]=f;
	siz[x]=1;
	for(int i=0;i<g[x].size();i++){
		int nx = g[x][i];
		if(nx!=f){
			dfs1(nx,x);
			siz[x]+=siz[nx];
			if(siz[nx]>siz[wc[x]])wc[x]=nx;//求重儿子
		}
	}
}
void dfs2(int x,int t){
	dfn[x]=++tot;//时间戳
	rdfn[tot]=x;//反向标记
	top[x]=t;//标记链头
	if(wc[x]){
		dfs2(wc[x],t);//优先访问重儿子
		for(int i=0;i<g[x].size();i++){
			int nx=g[x][i];
			if(nx!=wc[x]&&nx!=fa[x]){
				dfs2(nx,nx);
			}
		}
	}
}
void pushup(int p){
	sum(p)=sum(2*p)^sum(2*p+1);//向上更新
}
void build(int p,int l,int r){
	l(p)=l,r(p)=r;
	if(l==r){
		sum(p)=e[rdfn[l]];
		return;
	}
	int mid=(l+r)/2;
	build(2*p,l,mid);
	build(2*p+1,mid+1,r);
	pushup(p);
}
void change(int p,int x,int y){
	if(l(p)==r(p)){
		sum(p) = y;
		return;
	}
	int mid=(l(p)+r(p))/2;
	if(x<=mid)change(2*p,x,y);//在左子树
	else change(2*p+1,x,y);//在右子树
	pushup(p);
}
long long query(int p,int x,int y){
	if(x<=l(p)&&r(p)<=y){
		return sum(p);//在访问区间内
	}
	int mid=(l(p)+r(p))/2;
	long long ans=0;
	if(x<=mid)ans^=query(2*p,x,y);
	if(y>mid)ans^=query(2*p+1,x,y);
	return ans;
}
int ask(int x,int y){
	long long ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);//向上跳直至x,y在同一条链上
		ans^=query(1,dfn[top[x]],dfn[x]);
		x = fa[top[x]];
	}
	return ans^query(1,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]));
}
int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>e[i];
	}
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs1(1,0);
	dfs2(1,0);
	build(1,1,n);
	for(int i=1;i<=q;i++){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1){
			change(1,dfn[x],y);//单点修改
		}else{
			cout<<ask(x,y)<<endl;//求值
		}
	}
	return 0;
}