思路是首先点分治，对于每一个点 $x$ ，记录覆盖 $x$ 的所有连通块，信息包括连通块的重心 $G$ ，点 $x$ 所在子树 $from$ ，和距离重心的距离 $dis$ 。

用树状数组 $DS[0][x]$ 记录以 $x$ 为重心时连通块内所有的点，其大小为深度最深的点+2。其中因为重心到自己的距离为0，所以在 $update$ 和 $query$ 中位置 $p++$。树状数组不能出现0。同理， $DS[1][cnt]$ 代表 $x$ 所在子树的信息，其中 $cnt$ 进行了重编号。

结果全部RE。想知道为什么。谢谢大佬们QAQ！！！

#include <bits/stdc++.h>
#define N 100005
using namespace std;
int value[N],size[N],vis[N],f[N],head[N],tot,n,m;
int all,best,cnt,Maxdep1,Maxdep2,RT;
struct edge{
	int to,nex;
}e[N<<1];
struct node{
	int G,from,dis;
};
vector<node> a[N];
vector<int> DS[2][N];
int lowbit(int x){ return x&-x; }
void update(int x,int op,int p,int v){
	for(int i=p+1;i<=DS[op][x].size()-1;i+=lowbit(i)) DS[op][x][i]+=v;
}
int query(int x,int op,int p){
	int res=0; p=min(p+1,int(DS[op][x].size()-1));
	for(int i=p;i>=1;i-=lowbit(i)) res+=DS[op][x][i];
	return res;
}
void add(int x,int y){
	e[++tot].to=y;
	e[tot].nex=head[x];
	head[x]=tot;
}
void findroot(int x,int fa){
	f[x]=0; size[x]=1;
	for(int i=head[x];i;i=e[i].nex){
		int to=e[i].to;
		if(vis[to]||to==fa) continue;
		findroot(to,x);
		size[x]+=size[to]; f[x]=max(f[x],size[to]);
	}
	f[x]=max(f[x],all-size[x]);
	if(f[best]>f[x]) best=x;
}
void finddep(int x,int fa,int d){
	Maxdep2=max(Maxdep2,d); a[x].push_back(node{RT,cnt,d});
	for(int i=head[x];i;i=e[i].nex){
		int to=e[i].to;
		if(vis[to]||to==fa) continue;
		finddep(to,x,d+1);
	}
}
void solve(int x){
	a[x].push_back(node{x,0,0});
	Maxdep1=0; RT=x;
	for(int i=head[x];i;i=e[i].nex){
		int to=e[i].to;
		if(vis[to]) continue;
		Maxdep2=0; ++cnt; finddep(to,x,1);
		Maxdep1=max(Maxdep1,Maxdep2);
		DS[1][cnt].resize(Maxdep2+2);
	}
	DS[0][x].resize(Maxdep1+2);
	vis[x]=1;
	for(int i=head[x];i;i=e[i].nex){
		int to=e[i].to;
		if(vis[to]) continue;
		best=0; all=size[to];
		findroot(to,0); solve(best);
	}
}
void modify(int x,int v){
	for(int i=0;i<a[x].size();i++){
		int A=a[x][i].G,B=a[x][i].from,C=a[x][i].dis;
		update(A,0,C,v);
		if(!B) update(B,1,C,v);
	}
}
int ask(int x,int k){
	int ans=0; 
	for(int i=0;i<a[x].size();i++){
		int A=a[x][i].G,B=a[x][i].from,C=a[x][i].dis;
		if(k-C<=0) continue;
		ans+=query(A,0,k-C); 
		ans-=query(B,1,k-C);
	}
	return ans;
}
signed main(){
	ios::sync_with_stdio(false);
	int op,x,y,lastans;
	while(cin>>n>>m){
		memset(head,0,sizeof(head)); tot=0;
		for(int i=1;i<=n;i++) cin>>value[i];
		for(int i=1;i<n;i++) cin>>x>>y,add(x,y),add(y,x);
		best=0; f[0]=0x3f3f3f3f; all=n; 
		memset(vis,0,sizeof(vis)); cnt=0;
		findroot(1,0); solve(best);
		for(int i=1;i<=n;i++) modify(i,value[i]);
		lastans=0;
		for(int i=1;i<=m;i++){
			cin>>op>>x>>y; x^=lastans; y^=lastans;
			if(op==0) lastans=ask(x,y),cout<<lastans<<endl;
			else modify(x,y-value[x]); value[x]=y;
		}
	}
	return 0;
}