Top Tree 跑不过树剖，不知道是不是复杂度假了：

// Problem: P4751 【模板】"动态DP"&动态树分治（加强版）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4751
// Memory Limit: 250 MB
// Time Limit: 3500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define eb emplace_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef vector<int> vi;
bool Mbe;

const int N = 1e6 + 5;
const int inf = 0x3f3f3f3f;

int n, m, tot, rt;
int fa[N], sz[N], son[N], a[N];
vector<int> G[N];

struct T {
	int s[2][2];
	T () { memset(s, -inf, sizeof(s)); }
	T (int w) { s[0][1] = w, s[1][0] = s[0][0] = 0; }
	int qry() { return max(max(s[0][0], s[0][1]), max(s[1][0], s[1][1])); }
};

struct P {
	int x, y, op; T f;
	P () { }
	P (int _x, int _y, int _op, T _f) : 
		x(_x), y(_y), op(_op), f(_f) { }
};

struct S {
	int lc, rc, fa, sz; P vl;
	S () { }
	S (int _lc, int _rc, int _fa, int _sz, P _vl) :
		lc(_lc), rc(_rc), fa(_fa), sz(_sz), vl(_vl) { }
} t[N << 2];

#define ls(x) t[x].lc
#define rs(x) t[x].rc

void chk(int &x, int y) { x = (x > y ? x : y); }

P cp(const P &L, const P &R) {
	P res; res.x = L.x, res.y = R.y, res.op = 0;
	for (int i = 0; i <= 1; i++)
		for (int j = 0; j <= 1; j++)
			for (int k = 0; k <= 1; k++)
				chk(res.f.s[i][j], L.f.s[i][k] + R.f.s[k][j]);
	return res;
}

P rk(const P &L, const P &R) {
	P res; res.x = L.x, res.y = L.y, res.op = 1;
	for (int i = 0; i <= 1; i++)
		for (int j = 0; j <= 1; j++)
			for (int k = 0; k <= 1; k++)
				chk(res.f.s[i][j], L.f.s[i][j] + R.f.s[i][k]);
	return res;
}

int bld(vi::iterator l, vi::iterator r, auto op) {
	if (l == r - 1) return *l;
	int cur = 0, sum = 0; auto mid = l + 1;
	for (auto i = l; i != r; i++) sum += t[*i].sz;
	for (auto i = l; i != r; i++) {
		cur += t[*i].sz;
		if (cur * 2 <= sum) mid = i + 1;
	}
	int L = bld(l, mid, op), R = bld(mid, r, op);
	t[++tot] = S(L, R, 0, t[L].sz + t[R].sz, op(t[L].vl, t[R].vl)), t[L].fa = t[R].fa = tot;
	return tot;
}

void dfs1(int u, int f) {
	sz[u] = 1, fa[u] = f;
	t[u] = S(0, 0, 0, 1, P(f, u, -1, T(a[u])));
	for (int v : G[u]) {
		if (v == f) continue;
		dfs1(v, u), sz[u] += sz[v];
		if (sz[v] > sz[son[u]]) son[u] = v;
	}
}

int dfs2(int u) {
	vi p = { u };
	while (son[u]) {
		vi q = { son[u] };
		for (int v : G[u])
			if (v != son[u] && v != fa[u]) q.eb(dfs2(v));
		p.eb(bld(q.begin(), q.end(), rk)), u = son[u];
	}
	return bld(p.begin(), p.end(), cp);
}

void solve() {
	cin >> n >> m, tot = n;
	for (int i = 1; i <= n; i++) cin >> a[i];	
	for (int i = 1, u, v; i < n; i++)
		cin >> u >> v, G[u].eb(v), G[v].eb(u);
	dfs1(1, 0);
	rt = dfs2(1);
	int lst = 0;
	while (m--) {
		int x, y; cin >> x >> y, x ^= lst;
		a[x] = y, t[x].vl.f = T(y);
		while (x = t[x].fa) t[x].vl = (!t[x].vl.op ? cp : rk)(t[ls(x)].vl, t[rs(x)].vl);
		cout << (lst = t[rt].vl.f.qry()) << '\n';
	}
}

bool Med;
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
	#ifdef FILE
		freopen(".in", "r", stdin);
		freopen(".out", "w", stdout);
	#endif
	int T = 1;
	// cin >> T;
	while (T--) solve();
	cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
	return 0;
}