#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, m, c, x, y, ans, v[maxn];
vector<int> g[maxn], df[maxn];
int fa[maxn], fa_dis[maxn];
int d[maxn], f[maxn][20];
int sum, siz[maxn], weight[maxn] = {0x7fffffff}, centroid = 0;
bool vis[maxn];
int tree[maxn << 8], lc[maxn << 8], rc[maxn << 8], tot = 0, root[maxn][2], s[maxn], tots;
stack<int>stk;

void dfs(int u) {
	for (int v : g[u]) {
		if (d[v]) continue;
		d[v] = d[u] + 1;
		f[v][0] = u;
		for (int i = 1; i <= 18; ++i)
			f[v][i] = f[f[v][i - 1]][i - 1];
		dfs(v);
	}
}
int lca(int x, int y) {
	if (d[x] < d[y]) swap(x, y);
	for (int i = 18; i >= 0; --i)
		if (d[f[x][i]] >= d[y]) x = f[x][i];
	if (x == y) return x;
	for (int i = 18; i >= 0; --i)
		if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	return f[x][0];
}

int dist(int x, int y) {
	int l = lca(x, y);
	return d[x] + d[y] - 2 * d[l];
}

void update(int p) {
	tree[p] = tree[lc[p]] + tree[rc[p]];
}

void change(int &p, int l, int r, int x, int d) {
	if (!p) p = ++tot;
	if(tot > 5e5)
		tot = 0;
	if (l == r) {
		tree[p] += d;
		return;
	}
	int mid = (l + r) >> 1;
	x <= mid ? change(lc[p], l, mid, x, d) : change(rc[p], mid + 1, r, x, d);
	update(p);
}

int ask(int p, int l, int r, int y) {
	if (!p) return 0;
	if (l >= 0 && r <= y) return tree[p];
	int mid = (l + r) >> 1;
	int res = 0;
	if (0 <= mid) res += ask(lc[p], l, mid, y);
	if (y > mid) res += ask(rc[p], mid + 1, r, y);
	return res;
}

void calcsize(int u, int fa) {
	siz[u] = 1;
	weight[u] = 0;
	for (int v : g[u]) {
		if (v == fa || vis[v]) continue;
		calcsize(v, u);
		siz[u] += siz[v];
		weight[u] = max(weight[u], siz[v]);
	}
	weight[u] = max(weight[u], sum - siz[u]);
	if (weight[u] < weight[centroid]) centroid = u;
}
void build(int u) {
	vis[u] = true;
	for (int i = u; i; i = fa[i]) {
		change(root[i][0], 1, n, dist(u, i), v[u]);
		if(fa[i])
			change(root[i][1], 1, n, dist(fa[i], u), v[u]);
	}
	for (int v : g[u]) {
		if (vis[v]) continue;
		centroid = 0;
		weight[0] = 0x3fffffff;
		sum = siz[v];
		calcsize(v, u);
		calcsize(centroid, 0);
		fa[centroid] = u;
		df[u].push_back(centroid);
		build(centroid);
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; ++i) scanf("%d", &v[i]);
	for (int i = 1, u, v; i < n; ++i) {
		scanf("%d %d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	d[1] = 1;
	dfs(1);
	cout<<"dfs ok\n";
	sum = n;
	calcsize(1, 0);
	calcsize(centroid, 0);
	fa[centroid] = 0;
	build(centroid);
	cout<<"build ok\n";
	while (m--) {
		scanf("%d %d %d", &c, &x, &y);
		x ^= ans;
		y ^= ans;
		
		if (c) {
			for (int i = x; i; i = fa[i]) {
				change(root[i][0], 1, n, dist(x, i), y - v[x]);
				if(fa[i])
					change(root[i][1], 1, n, dist(fa[i], x), y - v[x]);
			}
			v[x] = y;
		} else {
			ans = ask(root[x][0], 1, n, y);
			for (int i = fa[x]; i; i = fa[i]) {
				int d = dist(i, x);
				ans += ask(root[i][0], 1, n, y - d);
				ans -= ask(root[i][1], 1, n, y - d);
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}

WA on #3

MEL on #2

RE on #1、4、5、6、7、8、9、10