TLE #2 #6 #10 玄关求条

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ull = unsigned ll;
using ld = long double;
using lll = __int128;
const int Mod = 1e9 + 7, mod = 998244353, inf = 0x3f3f3f3f, N = 1e5 + 10, M = 20, K = N * M;
const ll linf = 0x3f3f3f3f3f3f3f3f;
struct sgt{
	int rt[N], cnt = 0, ls[K << 2], rs[K << 2], v[K << 2];
	void modify(int& x, int l, int r, int cx, int val) {
		if (!x) x = ++cnt;
		if (l == r) {v[x] += val; return;}
		int mid = (l + r) >> 1;
		cx > mid ? modify(rs[x], mid + 1, r, cx, val) : modify(ls[x], l, mid, cx, val);
		v[x] = v[ls[x]] + v[rs[x]];
	}
	int query(int x, int l, int r, int ql, int qr) {
		if (l >= ql && r <= qr) return v[x];
		int mid = (l + r) >> 1, res = 0;
		if (ql <= mid) res += query(ls[x], l, mid, ql, qr);
		if (qr > mid) res += query(rs[x], mid + 1, r, ql, qr);
		return res;
	}
} s1, s2;

vector<int> g[N];
int maxn[N], siz[N], rt, nfa[N], fa[N][M], dep[N], n, q, sv[N], ltans;
bitset<N> vis;

int lca(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	for (int i = M - 1; ~i; i--) 
		if (dep[u] - (1 << i) >= dep[v]) u = fa[u][i];
	if (u == v) return u;
	for (int i = M - 1; ~i; i--) 
		if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}
int dis(int u, int v) {return dep[u] + dep[v] - 2 * dep[lca(u, v)];}
void dfs(int u, int f) {
	fa[u][0] = f;
	for (int i = 1; i < M; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for (int& v : g[u]) 
		if (v != f) dep[v] = dep[u] + 1, dfs(v, u);
}

void get_h(int u, int fa, int sum) {
	siz[u] = 1, maxn[u] = 0;
	for (int &v : g[u]) 
		if (v != fa && !vis[v]) get_h(v, u, sum), siz[u] += siz[v], maxn[u] = max(maxn[u], siz[v]);
	maxn[u] = max(maxn[u], sum - siz[u]);
	if (!rt || maxn[rt] > maxn[u]) rt = u;
}
void build(int u, int sum) {
	vis[u] = 1;
	for (int& v : g[u])
		if (!vis[v]) {
			int sz = (siz[v] < siz[u] ? siz[v] : sum - siz[u]);
			rt = 0, get_h(v, u, sz), nfa[rt] = u, build(rt, sz);
		}
}

void modify(int u, int v) {
	int now = u;
	while (now) {
		s1.modify(s1.rt[now], 0, n - 1, dis(now, u), v);
		if (nfa[now]) s2.modify(s2.rt[now], 0, n - 1, dis(nfa[now], u), v);
		now = nfa[now];
	}
}
int query(int u, int k) {
	int now = u, pre = 0, res = 0;
	while (now) {
		if (dis(now, u) > k) {pre = now, now = nfa[now]; continue;}
		res += s1.query(s1.rt[now], 0, n - 1, 0, k - dis(now, u));
		if (pre) res -= s2.query(s2.rt[pre], 0, n - 1, 0, k - dis(now, u));
		pre = now, now = nfa[now];
	}
	return res;
}

int main() {
	cin.tie(0) -> ios::sync_with_stdio(false);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> sv[i];
	for (int i = 1, u, v; i < n; i++) cin >> u >> v, g[u].push_back(v), g[v].push_back(u);
	dfs(1, 0), get_h(1, 0, n), build(rt, n);
	for (int i = 1; i <= n; i++) modify(i, sv[i]);
	while (q--) {
		int op, x, y;
		cin >> op >> x >> y;
		x ^= ltans, y ^= ltans;
		if (x > n) return 0;
		if (op) modify(x, y - sv[x]), sv[x] = y;
		else cout << (ltans = query(x, y)) << '\n';
	}
	return 0;
}