rt，套的树状数组，线段树能过，调不动了/kk。

代码：

#include<bits/stdc++.h>
//#define int long long
using namespace std;
namespace fast_IO {
#define IOSIZE 100000
int precision=3,POW[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};char ibuf[IOSIZE],obuf[IOSIZE],*p1=ibuf,*p2=ibuf,*p3=obuf;
#ifdef ONLINE_JUDGE
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
#endif
template<typename T>inline T read(){T s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)&&(ch!=EOF))if(ch==45)w=-1;if(ch==EOF)return 0;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*w;}template<typename T>inline bool read(T&s){s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)&&(ch!=EOF))if(ch==45)w=-1;if(ch==EOF)return 0;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*=w,1;}inline bool read(char&s){while(s=getchar(),isspace(s));return 1;}inline bool read(char*s){char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return 0;while(!isspace(ch))*s++=ch,ch=getchar();*s='\000';return 1;}template<typename T>inline void print(T x){if(x<0)putchar(45),x=-x;if(x>9)print(x/10);putchar(x%10+48);}inline void print(char x){putchar(x);}inline void print(char*x){while(*x)putchar(*x++);}inline void print(const char*x){for(int i=0;x[i];i++)putchar(x[i]);}inline bool read(std::string&s){s="";char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return 0;while(!isspace(ch))s+=ch,ch=getchar();return 1;}inline void print(std::string x){for(int i=0,n=x.size();i<n;i++)putchar(x[i]);}inline bool read(bool&b){char ch;while(ch=getchar(),isspace(ch));b=ch^48;return 1;}inline void print(bool b){putchar(b+48);}inline bool read(double&x){int a=0,b=0;char ch=getchar();bool f=0;while(ch<48||ch>57){if(ch==45)f=1;ch=getchar();}while(47<ch&&ch<58){a=(a<<1)+(a<<3)+(ch^48);ch=getchar();}if(ch!=46){x=f?-a:a;return 1;}ch=getchar();while(47<ch&&ch<58){b=(b<<1)+(b<<3)+(ch^48),ch=getchar();}x=b;while(x>1)x/=10;x=f?-a-x:a+x;return 1;}inline void print(double x){if(x<0){putchar(45),x=-x;}x=round((long double)x*POW[precision])/POW[precision],print((long long)x),putchar(46),x-=(long long)(x);for(int i=1;i<=precision;i++)x*=10,putchar(x+48),x-=(int)x;}template<typename T,typename...T1>inline int read(T& a,T1&...other){return read(a)+read(other...);}template<typename T,typename...T1>inline void print(T a,T1...other){print(a),print(other...);}struct Fast_IO{~Fast_IO(){fwrite(obuf,p3-obuf,1,stdout);}}io;template<typename T>Fast_IO& operator>>(Fast_IO&io,T&b){return read(b),io;}template<typename T>Fast_IO& operator<<(Fast_IO&io,T b){return print(b),io;}
#define cout io
#define cin io
#define endl '\n'
}using namespace fast_IO;
namespace TYX_YNXK{
	#define il inline
	#define bl bool
	#define ll long long
	#define vd void
	#define N 100005
	#define INF 0x3f3f3f3f
	#define DEBUG cout<<"You are right,but you are wrong"<<'\n'
	#define END cout<<"You are right,but you are right now"<<'\n'
	int n,m,dep[N],s[N],h[N],st[N][21],dfn[N],dcnt,fa[N],size[N],etot,ans;bl vis[N];//原树的 fa 不固定，这里的 fa 是淀粉树的 fa 
	struct edge{int to,nxt;}e[N<<1];
	il vd lj(int u,int v){e[++etot]=(edge){v,h[u]},h[u]=etot;}
	int sz[N],rt,maxx[N],all;//树的重心相关 
	vd getrt(int u,int fa){//求根 
		sz[u]=1,maxx[u]=0;
		for(int i=h[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to) if(v!=fa&&!vis[v]) getrt(v,u),sz[u]+=sz[v],maxx[u]=sz[v]>maxx[u]?sz[v]:maxx[u];
		if((maxx[u]=all-sz[u]>maxx[u]?all-sz[u]:maxx[u])<maxx[rt]) rt=u;
	}
	vd dfs(int u,int fa){
		st[dfn[u]=++dcnt][0]=fa;
		for(int i=h[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to) if(v!=fa) dep[v]=dep[u]+1,dfs(v,u);
	}
	#define CMP(a,b) (dfn[a]<dfn[b]?(a):(b))
	il vd init_RMQ(){
		for(int j=1;(1<<j)<=n;j++){
			for(int i=1;i+(1<<j)-1<=n;i++){
				st[i][j]=CMP(st[i][j-1],st[i+(1<<j-1)][j-1]);
			}
		}
	}
	il int lca(int u,int v){
		if(u==v) return u;
		u=dfn[u],v=dfn[v];
		if(u>v) swap(u,v);
		int d=__lg(v-u++);
		return CMP(st[u][d],st[v-(1<<d)+1][d]);
	}
	#define dis(a,b) (dep[a]+dep[b]-dep[lca(a,b)]*2)
	struct BIT{
		vector<int> t[N];
		il vd add(int u,int x,int v){for(;x<=size[u];x+=x&-x) t[u][x]+=v;}
		il int sum(int u,int x){int res=0;for(x=min(x,size[u]);x;x^=x&-x) res+=t[u][x];return res;}
	}T1,T2;
	vd build(int u,int point){
		vis[u]=1,size[u]=point+1,T1.t[u].resize(size[u]+1),T2.t[u].resize(size[u]+1);
		for(int i=h[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(vis[v]) continue;
			all=sz[v]<sz[u]?sz[u]:point-sz[u],getrt(v,rt=0),fa[rt]=u,build(rt,all);
		}
	}
	il vd update(int u,int val){
		for(int x=u;x;x=fa[x]){
			T1.add(x,dis(u,x)+1,val);
			if(fa[x]) T2.add(x,dis(u,fa[x])+1,val);
		}
	}
	il int query(int u,int k){
		int res=0;
		for(int x=u,y=0;x;x=fa[y=x]){
			if(dis(u,x)>k) continue;
			res+=T1.sum(x,k-dis(u,x)+1);
			if(y) res-=T2.sum(y,k-dis(u,x)+1);
		}
		return res;
	}
	signed main(){
		cin>>n>>m;maxx[0]=INF;
		for(int i=1;i<=n;i++) cin>>s[i];
		for(int i=1,u,v;i<n;i++) cin>>u>>v,lj(u,v),lj(v,u);
		dfs(1,0),init_RMQ();
		all=n,getrt(1,rt=0),build(rt,n);
		for(int i=1;i<=n;i++) update(i,s[i]);
		while(m--){
			int opt,u,v;cin>>opt>>u>>v,u^=ans,v^=ans;
			if(opt) update(u,v-s[u]),s[u]=v;
			else cout<<(ans=query(u,v))<<'\n';
		}
		return 0;
	}
}
signed main(){
	TYX_YNXK::main();
	return 0;
}