90分TLE#10，卡常，求调

#include<bits/stdc++.h>
using namespace std;
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const int INF = 0x3f3f3f3f;
const int N = 1000005;
int las, n, m, a[N];
int he[N], edge[N<<1], nxt[N<<1], cnt = 1;
int son[N], siz[N], fa[N], tot[N], f[N][2];
int id[N], dfn[N], idx, ed[N];
struct juzhen {
	int z[2][2];
	juzhen() {
		z[0][0] = z[0][1] = z[1][0] = z[1][1] = -INF;
	}
	inline juzhen operator*(const juzhen& z2) const __attribute__((always_inline)) {
		juzhen z3;
		register int z00 = z[0][0], z01 = z[0][1];
		register int z10 = z[1][0], z11 = z[1][1];
		register int z200 = z2.z[0][0], z201 = z2.z[0][1];
		register int z210 = z2.z[1][0], z211 = z2.z[1][1];
		z3.z[0][0] = max(z00 + z200, z01 + z210);
		z3.z[0][1] = max(z00 + z201, z01 + z211);
		z3.z[1][0] = max(z10 + z200, z11 + z210);
		z3.z[1][1] = max(z10 + z201, z11 + z211);
		return z3;
	}
} js[N];
inline int mmax(int x, int y){
	register int res = (x > y) ? x : y;
	return res;
}
inline void addedge(int u, int v){
	edge[++cnt] = v; nxt[cnt] = he[u]; he[u] = cnt;
	edge[++cnt] = u; nxt[cnt] = he[v]; he[v] = cnt;
}
struct Segment_Tree {
	int lc[N<<2], rc[N<<2];
	juzhen zy[N<<2];
	inline void pushup(int rt) __attribute__((always_inline)) {
		zy[rt] = zy[rt<<1] * zy[rt<<1|1];
	}
	void build(int rt, int l, int r) {
		lc[rt] = l; rc[rt] = r;
		if (l == r) {
			zy[rt] = js[id[l]];
			return;
		}
		int mid = (l + r) >> 1;
		build(rt<<1, l, mid);
		build(rt<<1|1, mid+1, r);
		pushup(rt);
	}
	void update(int rt, int x) {
		if (lc[rt] == rc[rt]) {
			zy[rt] = js[id[x]];
			return;
		}
		int mid = (lc[rt] + rc[rt]) >> 1;
		if (x <= mid) update(rt<<1, x);
		else update(rt<<1|1, x);
		pushup(rt);
	}
	juzhen query(int rt, int l, int r) {
		if (l <= lc[rt] && rc[rt] <= r) return zy[rt];
		int mid = (lc[rt] + rc[rt]) >> 1;
		if (r <= mid) return query(rt<<1, l, r);
		if (l > mid) return query(rt<<1|1, l, r);
		return query(rt<<1, l, mid) * query(rt<<1|1, mid+1, r);
	}
} tr;
void dfs1(int now, int p) {
	siz[now] = 1; fa[now] = p;
	for (int jj = he[now]; jj; jj = nxt[jj]) {
		int to = edge[jj];
		if (to == p) continue;
		dfs1(to, now);
		siz[now] += siz[to];
		if (siz[to] > siz[son[now]]) son[now] = to;
	}
}
void dfs2(int now, int chain) {
	tot[now] = chain;
	dfn[now] = ++idx;
	id[idx] = now;
	f[now][0] = 0;
	f[now][1] = a[now];
	ed[chain] = mmax(ed[chain], idx);
	js[now].z[0][0] = js[now].z[0][1] = 0;
	js[now].z[1][0] = a[now];
	js[now].z[1][1] = -INF;
	if (!son[now]) return;
	dfs2(son[now], chain);
	f[now][0] += mmax(f[son[now]][0], f[son[now]][1]);
	f[now][1] += f[son[now]][0];
	for (int jj = he[now]; jj; jj = nxt[jj]) {
		int to = edge[jj];
		if (to == fa[now] || to == son[now]) continue;
		dfs2(to, to);
		int max_to = mmax(f[to][0], f[to][1]);
		f[now][0] += max_to;
		f[now][1] += f[to][0];
		js[now].z[0][0] += max_to;
		js[now].z[0][1] = js[now].z[0][0];
		js[now].z[1][0] += f[to][0];
	}
}
void gai(int uu, int vv) {
	js[uu].z[1][0] += vv - a[uu];
	a[uu] = vv;
	juzhen la, ne;
	while (uu) {
		int top_u = tot[uu];
		int l = dfn[top_u], r = ed[top_u];
		la = tr.query(1, l, r);
		tr.update(1, dfn[uu]);
		ne = tr.query(1, l, r);
		
		uu = fa[top_u];
		if (uu == 0) break;
		int delta0 = mmax(ne.z[0][0], ne.z[1][0]) - mmax(la.z[0][0], la.z[1][0]);
		int delta1 = ne.z[0][0] - la.z[0][0];
		js[uu].z[0][0] += delta0;
		js[uu].z[0][1] = js[uu].z[0][0];
		js[uu].z[1][0] += delta1;
	}
}
char in[N*30], out[N*30], *p1 = in, *p2 = in, *p3 = out;
inline char gc() {
	return p1 == p2 && (p2 = (p1 = in) + fread(in, 1, 1<<20, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
	register int x = 0, f = 1;
	register char c = gc();
	while (c < 48 || c > 57) { if (c == '-') f = -1; c = gc(); }
	while (c >= 48 && c <= 57) x = x * 10 + c - 48, c = gc();
	return x * f;
}
inline void write(int x) {
	if (x < 0) *p3++ = '-', x = -x;
	static int sta[15];
	register int t = 0;
	do { sta[t++] = x % 10; x /= 10; } while (x);
	while (t--) *p3++ = sta[t] + '0';
	*p3++ = '\n';
}
signed main() {
	n = read(), m = read();
	for (int i = 1; i <= n; ++i) a[i] = read();
	for (int j = 1; j < n; ++j) {
		int u = read(), v = read();
		addedge(u, v);
	}
	dfs1(1, 0);
	dfs2(1, 1);
	tr.build(1, 1, n);
	
	while (m--) {
		int uu = read(), vv = read();
		uu ^= las;
		gai(uu, vv);
		juzhen ans = tr.query(1, dfn[1], ed[1]);
		las = mmax(ans.z[0][0], ans.z[1][0]);
		write(las);
	}
	fwrite(out, 1, p3 - out, stdout);
	return 0;
}