#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5;
const int INF = 0x3f3f3f3f;
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

//FastIO
using u32=unsigned;
struct IO_Tp{
	const static int _I_Buffer_Size=53<<20; char _I_Buffer[_I_Buffer_Size],*_I_pos=_I_Buffer;
	const static int _O_Buffer_Size=33<<20; char _O_Buffer[_O_Buffer_Size],*_O_pos=_O_Buffer; u32 m[10000];
	IO_Tp(){
		constexpr u32 e0='\0\0\0\1',e1='\0\0\1\0',e2='\0\1\0\0',e3='\1\0\0\0'; int x=0;
		for(u32 i=0,c0='0000';i!=10;++i,c0+=e0)
		for(u32 j=0,c1=c0;j!=10;++j,c1+=e1)
		for(u32 k=0,c2=c1;k!=10;++k,c2+=e2)
		for(u32 l=0,c3=c2;l!=10;++l,c3+=e3) m[x++]=c3;
		fread(_I_Buffer,1, _I_Buffer_Size,stdin);
	}
	~IO_Tp(){fwrite(_O_Buffer,1,_O_pos-_O_Buffer,stdout);}
	IO_Tp &operator>>(int &res){
		bool rev=0;
		while(!isdigit(*_I_pos)&&*_I_pos!='-') ++_I_pos;
		if(*_I_pos=='-') rev=1,++_I_pos; res=*_I_pos++-'0';
		while(isdigit(*_I_pos)) res=res*10+(*_I_pos++ - '0');
		if(rev) res=-res; return *this;
	}
	IO_Tp &operator<<(int x){
		if(x==0){*_O_pos++='0'; return *this;}
		static char _buf[35]; char *_pos=_buf+35;
		while(x>=10000) *--reinterpret_cast<u32*&>(_pos)=m[x%10000],x/=10000;
		*--reinterpret_cast<u32*&>(_pos)=m[x];
		_pos+=(x<1000)+(x<100)+(x<10);
		_O_pos=copy(_pos,_buf+35,_O_pos);
		return *this;
	}
	IO_Tp &operator<<(char ch){*_O_pos++=ch; return *this;}
} IO;
//FastIO

struct Matrix {
	int Map[2][2];
	
	Matrix() {
		memset(Map, 0, sizeof(Map));
	}
	
	int * operator[] (int d) {
		return Map[d];
	}
} tree[MAXN << 2], g[MAXN], ans, last, now;

Matrix operator * (Matrix m1, Matrix m2) {
	Matrix mm;
	mm[0][0] = max(m1[0][0] + m2[0][0], m1[0][1] + m2[1][0]);
	mm[1][0] = max(m1[1][0] + m2[0][0], m1[1][1] + m2[1][0]);
	mm[0][1] = max(m1[0][0] + m2[0][1], m1[0][1] + m2[1][1]);
	mm[1][1] = max(m1[1][0] + m2[0][1], m1[1][1] + m2[1][1]);
	return mm;
}

int f[MAXN][2], lastans;
int n, m, a[MAXN], EdgeCnt, head[MAXN], u, v;

struct Edge {
	int v, pre;
} e[MAXN << 3];

void AddEdge(int u, int v) {
	EdgeCnt++;
	e[EdgeCnt].v = v;
	e[EdgeCnt].pre = head[u];
	head[u] = EdgeCnt;
}

int cnt, fa[MAXN], dep[MAXN], son[MAXN], siz[MAXN], End[MAXN], rnk[MAXN], dfn[MAXN], top[MAXN];

void dfs1(int x);
void dfs2(int x, int t);

void Do(int to, int x) {
	fa[to] = x;
	dep[to] = dep[x] + 1;
	dfs1(to);
	siz[x] += siz[to];
	if(son[x] == -1 || siz[to] > siz[son[x]]) son[x] = to;
	f[x][1] += f[to][0];
	f[x][0] += max(f[to][0], f[to][1]);
}

void dfs1(int x) {
	son[x] = -1;
	siz[x] = 1;
	f[x][1] = a[x];
	for(int i = head[x]; i; i = e[i].pre) {
		int to = e[i].v;
		if(!dep[to]) Do(to, x);
	}
}

void Do2(int to, int x) {
	dfs2(to, to);
	g[x][0][0] += max(f[to][0], f[to][1]);
	g[x][1][0] += f[to][0];
}

void dfs2(int x, int t) {
	top[x] = t;
	dfn[x] = ++cnt;
	rnk[cnt] = x;
	End[t] = cnt;
	g[x][1][0] = a[x];
	g[x][1][1] = -INF;
	if(son[x] == -1) return;
	dfs2(son[x], t);
	for(int i = head[x]; i; i = e[i].pre) {
		int to = e[i].v;
		if(to != fa[x] && to != son[x]) Do2(to, x);
	}
	g[x][0][1] = g[x][0][0];
}

void push_up(int p) {
	tree[p] = tree[ls(p)] * tree[rs(p)];
}

void build(int p, int l, int r) {
	if(l == r) {
		tree[p] = g[rnk[l]];
		return;
	}
	int mid = (l + r) >> 1;
	build(ls(p), l, mid);
	build(rs(p), mid + 1, r);
	push_up(p);
}

Matrix query(int p, int nl, int nr, int l, int r) {
	if(nl <= l && r <= nr) return tree[p];
	int mid = (l + r) >> 1;
	if(nr <= mid) return query(ls(p), nl, nr, l, mid);
	if(mid < nl) return query(rs(p), nl, nr, mid + 1, r);
	return query(ls(p), nl, nr, l, mid) * query(rs(p), nl, nr, mid + 1, r);
}

void modify(int p, int l, int r, int pos) {
	if(l == r) {
		tree[p] = g[rnk[l]];
		return;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid) modify(ls(p), l, mid, pos);
	else modify(rs(p), mid + 1, r, pos);
	push_up(p);
}

void update(int x, int val) {
	g[x][1][0] += val - a[x];
	a[x] = val;
	while(x) {
		last = query(1, dfn[top[x]], End[top[x]], 1, n);
		modify(1, 1, n, dfn[x]);
		now = query(1, dfn[top[x]], End[top[x]], 1, n);
		x = fa[top[x]];
		g[x][0][0] += max(now[0][0], now[1][0]) - max(last[0][0], last[1][0]);
		g[x][0][1] = g[x][0][0];
		g[x][1][0] += now[0][0] - last[0][0];
	}
}

int main() {
	IO >> n >> m;
	for(int i = 1; i <= n; ++i) IO >> a[i];
	for(int i = 1; i < n; ++i) {
		IO >> u >> v;
		AddEdge(u, v);
		AddEdge(v, u);
	}
	dep[1] = 1;
	dfs1(1); dfs2(1, 1);
	build(1, 1, n);
	while(m--) {
		IO >> u >> v;
		u ^= lastans;
		update(u, v);
		ans = query(1, 1, End[1], 1, n);
		lastans = max(ans[0][0], ans[1][0]);
		IO << lastans << '\n';
	}
	return 0;
}

请问如何继续优化？