卡常？

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int rt[2][N];
struct sgt{
	#define mid ((le+ri)>>1)
	int s[N<<6],ls[N<<6],rs[N<<6],cnt;
	void push_up(int u){
		s[u]=s[ls[u]]+s[rs[u]];
	}
	void add(int &u,int le,int ri,int x,int k){
		if(!u) u=++cnt;
		if(le==ri){
			s[u]+=k;
			return;
		}
		if(x<=mid) add(ls[u],le,mid,x,k);
		else add(rs[u],mid+1,ri,x,k);
		push_up(u);
	}
	int que(int u,int le,int ri,int x,int y){
		if(!u) return 0;
		if(x<=le&&ri<=y){
			return s[u];
		}
		int res=0;
		if(x<=mid) res+=que(ls[u],le,mid,x,y);
		if(y>mid) res+=que(rs[u],mid+1,ri,x,y);
		return res;
	}
}t;
int n,q,a[N],val[N];
vector<int> e[N];
int fr[N][20],dep[N];
vector<int> k[N];
int dfa[N],kr;
vector<int> fas[N];
void dfs0(int u,int fa){
	fr[u][0]=fa;
	dep[u]=dep[fa]+1;
	for(int v:e[u]){
		if(v==fa) continue;
		dfs0(v,u);
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int j=16;j>=0;j--){
		int u=fr[x][j];
		if(u&&dep[u]>=dep[y]) x=u;
	}
	if(x==y) return x;
	for(int j=16;j>=0;j--){
		int u=fr[x][j],v=fr[y][j];
		if(u&&u!=v) x=u,y=v;
	}
	return fr[x][0];
}
int dis(int x,int y){
	int w=lca(x,y);
	return dep[x]+dep[y]-2*dep[w];
}
struct gen{
	int del[N];
	int sz[N],rt,sum;
	vector<int> f;
	void dfs0(int u,int fa){
		sz[u]=1;
		for(int v:e[u]){
			if(v==fa||del[v]) continue;
			dfs0(v,u);
			sz[u]+=sz[v];
		}
	}
	void dfs1(int u,int fa){
		int ok=1;
		for(int v:e[u]){
			if(v==fa||del[v]) continue;
			dfs1(v,u);
			if(sz[v]>sum/2) ok=0;
		}
		if(sum-sz[u]>sum/2) ok=0;
		if(ok) rt=u;
	}
	void cl(){
		for(int j:f){
			sz[j]=0;
		}
		rt=sum=0;
		f.clear();
	}
	int sol(int u,int fa){
		dfs0(u,0);
		sum=sz[u];
		dfs1(u,0);
		int r=rt;
		dfa[r]=fa;
		k[fa].push_back(r);
		del[r]=1;
		cl();
		for(int v:e[r]){
			if(del[v]) continue;
			sol(v,r);
		}
		return r;
	}
}t0;
void upd(int x,int k){
	int delta=k-val[x];
	val[x]=k;
	for(int u:fas[x]){
		int w=dis(x,u);
		t.add(rt[0][u],0,n,w,delta);
	}
	for(int i=0;i<(int)fas[x].size()-1;i++){
		int u=fas[x][i],v=fas[x][i+1];
		int w=dis(x,v);
		t.add(rt[1][u],0,n,w,delta);
	}
}
int que(int x,int k){
	int ans=0;
	ans+=t.que(rt[0][x],0,n,0,k);
	for(int i=0;i<(int)fas[x].size()-1;i++){
		int u=fas[x][i],v=fas[x][i+1];
		int w=dis(x,v);
		int maxi=k-w;
		if(maxi<0) continue;
		ans+=t.que(rt[0][v],0,n,0,maxi);
		ans-=t.que(rt[1][u],0,n,0,maxi);
	}
	return ans;
}
signed main(){
//	freopen("P6329_1.in","r",stdin);
//	freopen("P6329_1.txt","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs0(1,0);
	for(int j=1;j<=16;j++){
		for(int i=1;i<=n;i++){
			fr[i][j]=fr[fr[i][j-1]][j-1];
		}
	}
	kr=t0.sol(1,0);
	for(int i=1;i<=n;i++){
		int w=i;
		while(w){
			fas[i].push_back(w);
			w=dfa[w];
		}
	}
	for(int i=1;i<=n;i++){
		upd(i,a[i]);
	}
	int las=0;
	while(q--){
		int op,x,k;
		cin>>op>>x>>k;
		x^=las,k^=las;
		if(op==1){
			upd(x,k);
		}
		if(op==0){
			las=que(x,k);
			cout<<las<<"\n";
		}
	}
}