玄关求调感激不尽

#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
#define inf 1e12
#define debug(x) cerr << #x << ": " << x << endl
using namespace std;

const int MAXN = 1e6 + 7;
int a[MAXN], son[MAXN], siz[MAXN], fat[MAXN], dfn[MAXN], ant[MAXN], top[MAXN], down[MAXN], f[MAXN][2], g[MAXN][2], dfcnt, n, m;
vector<int> to[MAXN];

void init(int idx, int fa = 0) {
	siz[idx] = 1;
	fat[idx] = fa;
	f[idx][1] = a[idx];
	for (int i : to[idx]) {
		if (i == fa) continue;
		init(i, idx);
		f[idx][0] += max(f[i][0], f[i][1]);
		f[idx][1] += f[i][0];
		siz[idx] += siz[i];
		if (siz[i] > siz[son[idx]])
			son[idx] = i;
	}
}

void dfs(int idx) {
	dfn[idx] = ++dfcnt; ant[dfcnt] = idx;
	g[idx][1] = a[idx];
	if (son[idx]) top[son[idx]] = top[idx], dfs(son[idx]), down[idx] = down[son[idx]];
	else down[idx] = idx;
	for (int i : to[idx]) {
		if (i == fat[idx] || i == son[idx]) continue; ///////////
		g[idx][0] += max(f[i][0], f[i][1]);
		g[idx][1] += f[i][0];
		top[i] = i;
		dfs(i);
	}
}

struct matrix
{
	int val[2][2]{};
	int* operator[](int x) { return val[x]; }
	void dbg() { for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) cout << val[i][j] << ' '; cout << endl; }
};

matrix operator* (matrix u, matrix v)
{
	matrix ret;
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 2; k++)
				ret[i][j] = max(ret[i][j], u[i][k] + v[k][j]);
	return ret;
}

matrix id() { matrix I; I[0][1] = I[1][0] = -inf; return I; }

#define lsx (2 * idx)
#define rsx (2 * idx)
#define mid (l + r >> 1)
struct segtree
{
	matrix tree[MAXN];
	void pushup(int idx) { tree[idx] = tree[lsx] * tree[rsx]; }
	void build(int l = 1, int r = n, int idx = 1) {
		if (l == r) {
			tree[idx][0][0] = tree[idx][0][1] = g[ant[l]][0];
			tree[idx][1][0] = g[ant[l]][1]; tree[idx][1][1] = -inf;
			return;
		}
		build(l, mid, lsx);
		build(mid + 1, r, rsx);
		pushup(idx);
	}
	void add(int qidx, int val, int x, int y, int l = 1, int r = n, int idx = 1) {
		if (l == r) {
			tree[idx][x][y] += val;
			return;
		}
		if (qidx <= mid) add(qidx, val, x, y, l, mid, lsx);
		else add(qidx, val, x, y, mid + 1, r, rsx);
		pushup(idx);
	}
	matrix query(int ql, int qr, int l = 1, int r = n, int idx = 1) {
		if (ql <= l && r <= qr) return tree[idx];
		if (r < ql || qr < l) return id();
		return query(ql, qr, l, mid, lsx) * query(ql, qr, mid + 1, r, rsx);
	}
} tr;

matrix query(int idx) {
	//cout << "Querying: " << idx << ' ' << dfn[idx] << ' ' << dfn[down[idx]] << endl;
	return tr.query(dfn[idx], dfn[down[idx]]);
}

void change(int idx, int val) {
	int mem = idx;
	while (idx) {
		idx = top[idx];
		matrix val = query(idx);
		f[idx][0] = val[0][0];
		f[idx][1] = val[1][0];
		idx = fat[idx];
	}
	//debug("Memorized!");
	idx = mem;
	tr.add(dfn[idx], -a[idx], 1, 0);
	a[idx] = val;
	tr.add(dfn[idx], a[idx], 1, 0);
	while (idx) {
		idx = top[idx];
		matrix newval = query(idx);
		tr.add(dfn[fat[idx]], newval[0][0] - f[idx][0], 1, 0);
		tr.add(dfn[fat[idx]], max(newval[0][0], newval[1][0]) - max(f[idx][0], f[idx][1]), 0, 0);
		tr.add(dfn[fat[idx]], max(newval[0][0], newval[1][0]) - max(f[idx][0], f[idx][1]), 0, 1);
		idx = fat[idx];
	}
}

signed main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v;
		to[u].push_back(v);
		to[v].push_back(u);
	}
	init(1); top[1] = 1; dfs(1); tr.build();
	//cout << query(1)[0][0] << endl;
	while (m--) {
		int x, y; cin >> x >> y;
		change(x, y);
		matrix ret = query(1);
		cout << max(ret[0][0], ret[1][0]) << '\n';
	}
}