rt，调了一个下午+半个晚上。

自认为最可能挂的地方时 vector 的调用。

但是样例、讨论区的 hack 数据和第一个点本机测都过了，- 依然全部MLE。。。

谢谢帮忙看的大佬们。

#include<bits/stdc++.h>
#define maxn 100005
#define rg register
#define ll long long
#define put() putchar('\n')
using namespace std;
inline void read(int &x){
	int f=1;x=0;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	x*=f;
}
int deep[maxn],lg[maxn],w[maxn];
int n,m;
int head=1,h[maxn],fa[maxn];
struct yyy{
    int to,z;
    inline void add(int x,int y){
    	to=y;z=h[x];h[x]=head;
	}
}a[maxn*2];
namespace LCA{
    int fa[maxn][21];
    inline void dfs(int x,int pre){
    	rg int i;deep[x]=deep[pre]+1;fa[x][0]=pre;
    	for (i=1;i<=lg[deep[x]];i++) fa[x][i]=fa[fa[x][i-1]][i-1];
    	for (i=h[x];i;i=a[i].z) if (a[i].to^pre) dfs(a[i].to,x);
	}
    inline void init(void){
    	rg int i;
    	for (i=2;i<=n;i++) lg[i]=lg[i/2]+1;
    	dfs(1,0);
	}
	inline int lca(int x,int y){
		rg int i;
		if (deep[x]<deep[y]) swap(x,y);
		while (deep[x]>deep[y]) x=fa[x][lg[deep[x]-deep[y]]];
		if (x==y) return x;
		for (i=lg[deep[x]];i>=0;i--) if (fa[x][i]^fa[y][i]) x=fa[x][i],y=fa[y][i];
		return fa[x][0];
	}
	inline int getdis(int x,int y){
		return deep[x]+deep[y]-2*deep[lca(x,y)];
	}
}//倍增LCA
struct BIT{
	#define lowbit(x) ((x)&(-x))
	vector<int>f;int len;
	inline void init(int size){f.resize(size);len=f.size()-1;}
	inline void add(int x,int y){rg int i;for (i=x+1;i<=len;i+=lowbit(i)) f[i]+=y;}
	inline int query(int x){rg int i,sum=0;for (i=min(x+1,len);i;i-=lowbit(i)) sum+=f[i];return sum;}
}t[maxn][2];
int Max[maxn],size[maxn],root,vis[maxn];
int sum;
inline int getroot(int x,int pre){
	rg int i;size[x]=1;Max[x]=0;
	for (i=h[x];i;i=a[i].z)
	    if (a[i].to!=pre&&!vis[a[i].to]){
	    	getroot(a[i].to,x);
	    	size[x]+=size[a[i].to];
	    	Max[x]=max(Max[x],size[a[i].to]);
		}
	Max[x]=max(Max[x],sum-size[x]);
	if (!root||Max[root]>Max[x]) root=x;
}//找根
inline void solve(int x){
	rg int i;vis[x]=1;
	t[x][0].init(sum+3);
	t[x][1].init(sum+3);//printf("%d ",sum);
	for (i=h[x];i;i=a[i].z)
	    if (!vis[a[i].to]){
	    	root=0;sum=size[a[i].to];getroot(a[i].to,0);
	    	fa[root]=x;solve(root);
		}
}//建点分树
inline void Update(int x,int w){
	rg int i;
	for (i=x;i;i=fa[i]) t[i][0].add(LCA::getdis(x,i),w);
	for (i=x;fa[i];i=fa[i]) t[i][1].add(LCA::getdis(x,fa[i]),w);
}//更新
signed main(){
//	freopen("P6329_1.in","r",stdin);
//	freopen("1.out","w",stdout);
	rg int i,x,y,op,ans=0;
	read(n);read(m);
	for (i=1;i<=n;i++) read(w[i]);
	for (i=1;i<n;i++) {
		read(x);read(y);
		a[++head].add(x,y);
		a[++head].add(y,x);
	}
	LCA::init();
	sum=n;
	getroot(1,0);
	solve(root);
	for (i=1;i<=n;i++) Update(i,w[i]);
	while (m--){
		read(op);read(x);read(y);
		x^=ans;y^=ans;
		if (op==1) Update(x,y-w[x]),w[x]=y;
		else {
			ans=t[x][0].query(y);
			for (i=x;fa[i];i=fa[i]) {
				int dis=LCA::getdis(x,fa[i]);
				if (dis<=y) ans+=t[fa[i]][0].query(y-dis)-t[i][1].query(y-dis);
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}