代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=0x7fffffff;
const int N=100005;
int tot,fa[N],size[N],dep[N],top[N],dfn[N],pre[N],son[N],bot[N];
int n,m,a[N],dp[N][2],head[N<<2],cnt;
inline int read() {
	int x=0,f=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) f|=(ch=='-');
    for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
	return f?-x:x;
}
void print(int x) {
	if(x<0) putchar('-'),x=-x;
	if(x>9) print(x/10);
	putchar(x%10+48);
}
struct node{
	int next,to,w;
}e[N<<2];
void add(int u,int v) {
	e[++cnt].next=head[u];
	e[cnt].to=v;
	head[u]=cnt;
}
struct miu{
	int c[2][2];
	miu(){}
	miu(int a1,int a2,int b1,int b2) {
		c[0][0]=a1;
		c[0][1]=a2;
		c[1][0]=b1;
		c[1][1]=b2;
	}
	void clear(){
		memset(c,0,sizeof(c));
	}
	int *operator[](int x) {
		return c[x];
	}
	miu operator*(miu b) const {
	    miu ans;
	    ans.clear();
	    for (int i=0;i<2;++i) {
	    	for (int j=0;j<2;++j) {
	    		for (int k=0;k<2;++k) {
	    			ans[i][j]=max(ans[i][j],c[i][k]+b[k][j]);
				}
			}
		}
		return ans;
	}
}tree[N<<2],tmp[N];
namespace sp{
	void dfs1(int now,int Fa) {
		size[now]=1; fa[now]=Fa; dep[now]=dep[Fa]+1;
	    for (int i=head[now];i;i=e[i].next) {
	    	if (e[i].to==Fa) continue;
	    	dfs1(e[i].to,now);
			size[now]+=size[e[i].to];
			if (size[e[i].to]>size[son[now]]||!son[now]) son[now]=e[i].to; 
		}
		//cout<<"     "<<now<<" "<<son[now]<<endl;
	}
	void dfs2(int now,int Top) {
		dfn[now]=++tot; pre[tot]=now; top[now]=Top;
		if (son[now]) dfs2(son[now],Top),bot[now]=bot[son[now]];
		else bot[now]=now;
		for (int i=head[now];i;i=e[i].next) {
			if (e[i].to==fa[now]||e[i].to==son[now]) continue;
			dfs2(e[i].to,e[i].to);
		}
	}
}
void dfs(int now) {
	dp[now][0]=0; dp[now][1]=a[now];
	for(int i=head[now];i;i=e[i].next) {
		if (e[i].to==fa[now]) continue;
		dfs(e[i].to);
		dp[now][1]+=dp[e[i].to][0];
		dp[now][0]+=max(dp[e[i].to][1],dp[e[i].to][0]);
	}
}
namespace ss{
	#define lson pos<<1
	#define rson pos<<1|1
	void build(int pos,int l,int r) {
		if (l==r) {
			int now=pre[l],f0=0,f1=a[now];
			for (int i=head[now];i;i=e[i].next) {
				if (e[i].to=fa[now]||e[i].to==son[now]) continue; 
			    f1+=dp[e[i].to][0];
			    f0+=max(dp[e[i].to][0],dp[e[i].to][1]);
			}
            tree[pos]=tmp[l]=miu(f0,f0,f1,-inf);
            return ;
		}
		int mid=l+r>>1;
		build(pos<<1,l,mid);
		build(pos<<1|1,mid+1,r);
		tree[pos]=tree[lson]*tree[rson];
	}
	void change(int pos,int l,int r,int k) {
		if (l==r) {
			tree[pos]=tmp[l]; 
			return ;
		}
		int mid=l+r>>1;
		if (k<=mid) change(lson,l,mid,k);
		else change(rson,mid+1,r,k);
		tree[pos]=tree[lson]*tree[rson];
	}
	miu query(int pos,int l,int r,int L,int R) {
		if (l>=L && r<=R) return tree[pos];
		int mid=l+r>>1;
		if (R<=mid) return query(lson,l,mid,L,R);
		else if (mid<L) return query(rson,mid+1,r,L,R);
		else return query(lson,l,mid,L,R)*query(rson,mid+1,r,L,R);
	}
}
void update(int now,int k) {
	tmp[dfn[now]][1][0]+=k-a[now]; 
	a[now]=k;
	while(now) {
		miu last=ss::query(1,1,n,dfn[top[now]],dfn[bot[now]]);
		ss::change(1,1,n,dfn[now]);
		miu b=ss::query(1,1,n,dfn[top[now]],dfn[bot[now]]);
	    now=fa[top[now]];
	    if (!now) break;
	    int p=dfn[now];
	    tmp[p][0][0]=tmp[p][0][1]=tmp[p][0][0]+max(b[0][0],b[1][0])-max(last[0][0],last[1][0]);
	    tmp[p][1][0]=tmp[p][1][0]+b[0][0]-last[0][0];
	}
}
signed main(){
    n=read(); m=read();
    for (int i=1;i<=n;++i) {
    	a[i]=read();
	}
    for (int i=1;i<n;++i) {
    	int x,y; 
    	x=read(); y=read();
	    add(x,y); add(y,x);
	}
	sp::dfs1(1,0); sp::dfs2(1,1); dfs(1);
	ss::build(1,1,n);
	for (int i=1;i<=m;++i) {
		int x=read(),y=read();
		update(x,y);
		miu ans=ss::query(1,1,n,1,dfn[bot[1]]);
		print(max(ans[0][0],ans[1][0]));
		putchar('\n');
	}
	return 0;
}