马蜂优良，思路清晰，详细注释点分树求调

#include <bits/stdc++.h>
#define PII pair <int, int>
#define ll long long
#define MP make_pair
#define PB push_back
using namespace std;
constexpr int N = 1e5 + 10, M = 25;
int n, q, K, a[N], f[N][M], fat[N], d[N], sz[N], wei[N], num, vis[N], rt, ans;
vector <int> g[N];
char *p1, *p2, buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline int read ()
{
	int x = 0, f = 1;
	char ch = nc ();
	while (ch < 48 || ch > 57)
	{
		if (ch == '-') f = -1;
		ch = nc ();
	}
	while (48 <= ch && ch <= 57) x = x * 10 + ch - 48, ch = nc ();
	return x * f;
}
//lca及预处理
void dfs (int u, int fa)
{
    d[u] = d[fa] + 1, f[u][0] = fa;
    for (int i = 1; i <= K; i++) f[u][i] = f[f[u][i - 1]][i - 1];
    for (int i = 0; i < (int) g[u].size (); i++)
    {
        int v = g[u][i];
        if (v == fa) continue;
        dfs (v, u);
    }
}
inline int lca (int x, int y)
{
    if (d[x] > d[y]) swap (x, y);
    for (int i = K; i >= 0; i--) if (d[f[y][i]] >= d[x]) y = f[y][i];
    if (x == y) return x;
    for (int i = K; i >= 0; i--) if (f[y][i] != f[x][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}
inline int dis (int x, int y) {return d[x] + d[y] - 2 * d[lca (x, y)];}
struct node 
{
    int ls, rs, val;
    #define ls(p) t[p].ls
    #define rs(p) t[p].rs
    #define val(p) t[p].val
};
//动态开点线段树
struct tree
{
    node t[2 * N * M];
    int root[N], cnt = 0;
    void change (int &p, int l, int r, int pos, int x)
    {
        if (!p) p = ++cnt;
        if (l == r) {val (p) += x; return;}
        int mid = (l + r) >> 1;
        if (pos <= mid) change (ls (p), l, mid, pos, x);
        else change (rs (p), mid + 1, r, pos, x);
        val (p) = val (ls (p)) + val (rs (p));
    }
    int query (int p, int l, int r, int L, int R)
    {
        if (!p) return 0;
        if (L <= l && r <= R) return val (p);
        int mid = (l + r) >> 1;
        if (l <= mid && r <= mid) return query (ls (p), l, mid, L, R);
        else if (l > mid && r > mid) return query (rs (p), mid + 1, r, L, R);
        else return query (ls (p), l, mid, L, R) + query (rs (p), mid + 1, r, L, R);
    }
} f1, f2;
//获得根节点
void get_root (int u, int fa)
{
    sz[u] = 1, wei[u] = 0;
    for (int i = 0; i < (int) g[u].size (); i++)
    {
        int v = g[u][i];
        if (v == fa || vis[v]) continue;
        get_root (v, u);
        sz[u] += sz[v];
        wei[u] = max (wei[u], sz[v]);
    }
    wei[u] = max (wei[u], num - sz[u]);
    if (wei[u] < wei[rt]) rt = u;
}
//建树
void calc (int u)
{
    int now = num; vis[u] = 1;
    for (int i = 0; i < (int) g[u].size (); i++)
    {
        int v = g[u][i];
        if (vis[v]) continue;
        rt = 0, num = sz[v] > sz[u] ? now - sz[u] : sz[v];
        get_root (v, u);
        fat[rt] = u;
        calc (rt);
    }
}
//增加某个点
void update (int pos, int x)
{
    int now = pos;
    while (now)
    {
        f1.change (f1.root[now], 0, n - 1, dis (pos, now), x);
        if (fat[now]) f2.change (f2.root[now], 0, n - 1, dis (pos, fat[now]), x);
        now = fat[now];
    }
}
//查询某个点
int query (int pos, int x)
{
    int now = pos, last = 0, ret = 0;
    while (now)
    {
        int len = dis (now, pos);
        if (len > x) {last = now, now = fat[now]; continue;}
        ret += f1.query (f1.root[now], 0, n - 1, 0, x - len);
        if (last) ret -= f2.query (f2.root[last], 0, n - 1, 0, x - len);
        last = now; now = fat[now];
    }
    return ret;
}
int main()
{
	// freopen ("C:\\Users\\26249\\Downloads\\P6329_1.in", "r", stdin);
	// freopen ("C:\\Users\\26249\\Downloads\\P6329.out", "w", stdout);
    n = read (), q = read ();
    wei[0] = INT_MAX, num = n;
    K = log2 (n);
    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[u].PB (v), g[v].PB (u);}
    //建树
    dfs (1, 0);    
    get_root (1, 0);
    calc (rt);
    for (int i = 1; i <= n; i++) update (i, a[i]);
    while (q--)
    {
        int op, x, y;
        op = read (), x = read (), y = read ();
        x ^= ans, y ^= ans;
        if (!op) {ans = query (x, y); cout << ans << "\n";}
        else {update (x, y - a[x]), a[x] = y;}
    }
    return 0;
}
/*
8 1
1 10 100 1000 10000 100000 1000000 10000000
1 2
1 3
2 4
2 5
3 6
3 7
3 8
0 3 1
*/