RT，几个点随机 TLE，时间都是 2s 多一点，不知道是什么问题。

#include <bits/stdc++.h>
using namespace std;
int n, m, p, x, y, op, tsiz, ans, R, rt, mn, a[100010], h[100010], siz[100010], vis[100010], f[100010], dep[100010], F[100010][18];
struct node{
	int x, y, next;
}d[200010];
inline int read(){
	int s=0, w=1; char ch=getchar();
	while (ch<'0'||ch>'9'){if(ch=='-') w=-1; ch=getchar();}
	while (ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-48; ch=getchar();}
	return s*w;
}
void add(int x, int y){
	d[++p].y = y, d[p].next = h[x], h[x] = p;
}
void dfs(int x, int fa){
	dep[x] = dep[fa] + 1;
	for (int i=0; i<17; i++){
		F[x][i+1] = F[F[x][i]][i];
	}
	for (int i=h[x]; i; i=d[i].next){
		int y = d[i].y;
		if (y == fa) continue;
		F[y][0] = x;
		dfs(y, x);
	}
}
int LCA(int x, int y){
	if (dep[x] < dep[y]) swap(x, y);
	for (int i=17; i>=0; i--){
		if (dep[F[x][i]] >= dep[y]) x = F[x][i];
		if (x == y) return x;
	}
	for (int i=17; 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){
	return dep[x] + dep[y] - 2 * dep[LCA(x, y)];
}
void dfs1(int x, int fa){
	int mx = 0;
	siz[x] = 1;
	for (int i=h[x]; i; i=d[i].next){
		int y = d[i].y;
		if (y == fa || vis[y]) continue;
		dfs1(y, x);
		siz[x] += siz[y];
		mx = max(mx, siz[y]);
	}
	mx = max(mx, tsiz - siz[x]);
	if (mx < mn) mn = mx, rt = x;
}
void solve(int x, int fa){
	vis[x] = 1;
	for (int i=h[x]; i; i=d[i].next){
		int y = d[i].y;
		if (y == fa || vis[y]) continue;
		tsiz = siz[y], mn = 1e9, rt = 0;
		dfs1(y, x);
		dfs1(rt, 0);
		f[rt] = x;
		solve(rt, 0);
	}
}
struct segment{
	int cnt = 0, t[100010];
	struct point{
		int l, r, s;
	}d[10000010];
	void pushup(int p){
		d[p].s = d[d[p].l].s + d[d[p].r].s;
	}
	void modify(int &p, int l, int r, int x, int y){
		if (!p) p=++cnt;
		if (l == r){
			d[p].s += y;
			return ;
		}
		int mid = l + r >> 1;
		if (x <= mid) modify(d[p].l, l, mid, x, y);
		else modify(d[p].r, mid+1, r, x, y);
		pushup(p);
	}
	int query(int p, int l, int r, int x, int y){
		if (x <= l && r <= y) return d[p].s;
		int mid = l + r >> 1, ret = 0;
		if (x <= mid) ret += query(d[p].l, l, mid, x, y);
		if (y > mid) ret += query(d[p].r, mid+1, r, x, y);
		return ret;
	}
}S, T;
int main(){
	n=read(), m=read();
	for (int i=1; i<=n; i++){
		a[i]=read();
	}
	for (int i=1; i<n; i++){
		x=read(), y=read();
		add(x, y); add(y, x);
	}
	mn = 1e9, tsiz = n;
	dfs(1, 0);
	dfs1(1, 0);
	dfs1(R=rt, 0);
	solve(rt, 0);//建立点分树
	for (int i=1; i<=n; i++){
		//每个点i对祖先线段树的贡献，暴力跳祖先
		int now = i;
		while (now){
			S.modify(S.t[now], 0, n, dist(i, now), a[i]);
			if (f[now]) T.modify(T.t[now], 0, n, dist(i, f[now]), a[i]);//一个节点的儿子的子树中，到它距离<=k的点权和 
			now = f[now];
		}
	}
	for (int i=1; i<=m; i++){
		op=read(), x=read(), y=read();
		x ^= ans, y ^= ans;
		if (op == 1){
			int now = x;
			while (now){
				S.modify(S.t[now], 0, n, dist(x, now), y-a[x]);
				if (f[now]) T.modify(T.t[now], 0, n, dist(x, f[now]), y-a[x]);//一个节点的儿子的子树中，到它距离<=k的点权和 
				now = f[now];
			}
			a[x] = y;
		}
		else{
			ans = 0;
			int now = x, lst = 0;
			while (now){
				int dis = dist(now, x);
				if (dis > y){
					lst = now, now = f[now];
					continue;
				}
				ans += S.query(S.t[now], 0, n, 0, y-dis);
				if (lst) ans -= T.query(T.t[lst], 0, n, 0, y-dis);
				lst = now, now = f[now];
			}
			printf ("%d\n", ans);
		}
	}
	return 0;
}