_{（自己写的动态点分治巨垃圾，常数是别人的两倍）}
用动态开点线段树死活过不去，学了一波大佬用 vector 开树状数组立马就卡过去了

考虑点分树的做法，在点分树上每个点以距离为下标建一棵线段树，每次询问查询子树的贡献，再暴力向上跳合并父节点来自其它节点的贡献。

因为子树树形被破坏，在做减法时，子节点子树对父节点的贡献不能用子树维护的信息 + 连向父节点的边的贡献得到，考虑在每个节点再维护一个线段树，按距离建树用来统计子树内的节点到其父节点距离为 p 的点权和，这样便可以暴力爬树统计子树外的节点的贡献。

理论复杂度为 $O(n{\log }^{2}n)$，但常数巨大，况且还要上动态开点线段树。

采用了别人的用vector开树状数组的做法，首先对空间进行分析：
动态开点线段树：由于树高 $log$，每次维护要暴力向上爬维护路径上所有节点的信息，显然一个点最多在线段树插入 $\log$ 次，每次插入是单点修改，最多需要新建 $\log$ 个节点，理论空间复杂度上限是 $n{\log }^{2}n$

$vector$ 开树状数组：$vector$ 开树状数组最主要要掌握每个节点要开的大小，由于我们维护的是子树信息并且以距离为关键字进行建树维护。每个节点的树状数组大小 = 该节点在点分树上子节点的个数。由于点分树每个节点都是这棵子树的重心，每个子节点的 $size$ 的大小大约为父节点 $size$ 的 $\frac{1}{2}$，总空间大约为 $n+\frac{1}{2}n+\frac{1}{2}n+\frac{1}{4}n+...+1$，大概是 $n\log n$ 级别（不是很准确，大概是这个数字左右）

$vector$ 调用 $resize(size)$ 函数就可以分配，$size$ 大小的空间，如果再传一个参数，将全部赋值为第二个参数的值，最后用树状数组比用线段树快一倍以上。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
typedef long long ll;
#define lowbit(i) (i & (-i))
struct Graph {
    
	int head[maxn], to[maxn << 1], cnt, nxt[maxn << 1], w[maxn << 1];
	void init() {
    
		memset(head,-1,sizeof head);
		cnt = 0;
	}
	void add(int u,int v,int c) {
    
		to[cnt] = v;
		nxt[cnt] = head[u];
		w[cnt] = c;
		head[u] = cnt++;
		
		to[cnt] = u;
		nxt[cnt] = head[v];
		w[cnt] = c;
		head[v] = cnt++;
	}
}G;
vector<int> sum[maxn],fsum[maxn];					//动态开点树状数组 
void modify(vector<int> &tree,int p,int v) {
    
	if (p == 0)
		tree[0] += v;
	else {
    
		for (int i = p; i < tree.size(); i += lowbit(i))
			tree[i] += v;	
	}
}
int ask(vector<int> &tree,int k) {
    
	k = min(k,(int) tree.size() - 1);
	int ans = tree[0];
	for (int i = k; i; i -= lowbit(i))
		ans += tree[i];
	return ans;
}
int st[maxn][30],d[maxn],cnt,a[maxn];
int fir[maxn],vis[maxn],f[maxn],root,sz[maxn],siz,p[maxn];
int n,q,RT;
inline int read()
{
    
	int x=0,f=1;char ch;
	while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void dfs1(int u,int fa) {
    			//预处理深度,st表，以及欧拉序 
	fir[u] = ++cnt; st[cnt][0] = u;
	for (int i = G.head[u]; i + 1; i = G.nxt[i]) {
    
		int v = G.to[i];
		if (v == fa) continue;
		d[v] = d[u] + G.w[i];
		dfs1(v,u);
		st[++cnt][0] = u;
	}
}
void dfs2(int u,int fa) {
    			//求一棵子树的重心 
	sz[u] = 1; f[u] = 0;
	for (int i = G.head[u]; i + 1; i = G.nxt[i]) {
    
		int v = G.to[i];
		if (v == fa || vis[v]) continue;
		dfs2(v,u);
		sz[u] += sz[v];
		if (sz[v] > f[u]) f[u] = sz[v];
	}
	if (siz - sz[u] > f[u]) f[u] = siz - sz[u];
	if (!root || f[u] < f[root]) root = u;
}
void dfs3(int u,int fa) {
     			//点分构建点分树 
	vis[u] = 1;
	int all = siz;
	sum[u].resize(all + 1), fsum[u].resize(all + 1);
	for (int i = G.head[u]; i + 1; i = G.nxt[i]) {
    
		int v = G.to[i];
		if (v == fa || vis[v]) continue;
		root = 0, siz = sz[v]; 
		if (siz > sz[u]) siz = all - sz[u];
		dfs2(v,u);
		p[root] = u;	//构建点分树
		dfs3(root,u); 
	}
}
int cal(int u,int v) {
    
	return d[u] < d[v] ? u : v;
}
int getlca(int x,int y) {
    
	if (fir[x] > fir[y]) swap(x,y);
	int p = log2(fir[y] - fir[x] + 1);
	return cal(st[fir[x]][p],st[fir[y] - (1 << p) + 1][p]);
}
int getdis(int x,int y) {
    
	return d[x] + d[y] - 2 * d[getlca(x,y)];
}
void prework() {
    
	dfs1(1,0);
	for (int i = 1; i <= log2(cnt); i++)
		for (int j = 1; j + (1 << i) - 1 <= cnt; j++)
			st[j][i] = cal(st[j][i - 1],st[j + (1 << (i - 1))][i - 1]);
	root = 0, siz = n; dfs2(1,0);
	RT = root; dfs3(root,0);		//保留第一次的根节点，并构建点分树 
}
void update(int x,int y) {
    
	for (int i = x; i; i = p[i]) {
    
		int dist = getdis(x,i);
		modify(sum[i],dist,y);
		if (p[i]) modify(fsum[i],getdis(x,p[i]),y);
	}
}
int qry(int x,int k) {
    
	int tmp = ask(sum[x],k);
	for (int i = x; p[i]; i = p[i]) {
    
		int dist = getdis(x,p[i]);
		if (dist <= k) {
    
			tmp += ask(sum[p[i]],k - dist);
			tmp -= ask(fsum[i],k - dist);	
		}
	}
	return tmp;
}
int main() {
    
	n = read(); q = read();
	G.init();
	for (int i = 1; i <= n; i++) {
    
		a[i] = read();
	}
	for (int i = 1; i < n; i++) {
    
		int u,v; u = read(); v = read();
		G.add(u,v,1);
	}
	prework();
	for (int i = 1; i <= n; i++)
		update(i,a[i]);
	int ans = 0;
	while (q--) {
    
		int op,x,y; op = read(); x = read(); y = read();
		x ^= ans; y ^= ans;
		if (op == 1) {
    
			update(x,y - a[x]);
			a[x] = y;
		} else {
    
			ans = qry(x,y);
			printf("%d\n",ans);	
		}
	}
	return 0;
}