#include<bits/stdc++.h>
#define ll long long
#define lc(x) x<<1
#define rc(x) x<<1|1
#define endl '\n'
using namespace std;
const int inf=1e9+7,N=1e5+10;
//----------------------------
struct jz{
	int a[3][3],n,m;
	jz(){memset(a,0,sizeof(a));}
}dw;
jz operator*(jz &a,jz &b){
	jz c;
	memset(c.a,-inf,sizeof(c.a));
	c.n=a.n,c.m=b.m;
	for(int i=1;i<=c.n;i++){
		for(int j=1;j<=c.m;j++){
			for(int k=1;k<=a.m;k++)c.a[i][j]=max(c.a[i][j],a.a[i][k]+b.a[k][j]);
		}
	}
	return c;
}
void print(jz a){
	for(int i=1;i<=a.n;i++){
		for(int j=1;j<=a.m;j++)printf("%lld ",a.a[i][j]);
		printf("\n");
	}
		puts("");
}
//-------------------------------------矩阵 
jz t[N<<2],a[N];
int son[N],size[N],dfn[N],top[N],dep[N],tot,fa[N],last[N],en[N],nfd[N];
int f[N][2],g[N][2],n,val[N],m,x,y;
vector<int> e[N];
inline int update(int n){t[n]=t[rc(n)]*t[lc(n)];}
void build(int l,int r,int n){
	if(l==r){t[n]=a[nfd[l]];return;}
	int mid=l+r>>1;
	build(l,mid,lc(n));
	build(mid+1,r,rc(n));
	update(n);
}
void turn(int l,int r,int n,int x,jz y){
	if(l==r){
		t[n]=y;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid)turn(l,mid,lc(n),x,y);
	else turn(mid+1,r,rc(n),x,y);
	update(n);
}
jz ask(int l,int r,int n,int lx,int rx){
	if(l>=lx&&r<=rx)return t[n];
	int mid=l+r>>1;
	if(rx<=mid)return ask(l,mid,lc(n),lx,rx);
	if(lx>mid)return ask(mid+1,r,rc(n),lx,rx);
	jz a=ask(mid+1,r,rc(n),lx,rx),b=ask(l,mid,lc(n),lx,rx);
	return a*b;
}
//-------------------------------------线段树 
void dfs1(int u,int faa,int len){
    size[u]=1;
    dep[u]=len;
    fa[u]=faa;
    f[u][1]=val[u];
    for(int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v==faa)continue;
        dfs1(v,u,len+1);
        size[u]+=size[v];
        if(size[v]>size[son[u]])son[u]=v;
        f[u][0]+=max(f[v][0],f[v][1]);
        f[u][1]+=f[v][0];
    }
    if(son[u]==0)son[u]=u;
}
void dfs(int u,int x){
    last[u]=dfn[u]=++tot;
    nfd[tot]=u;
    top[u]=x;
    if(son[u]==u){
    	en[u]=u;
    	return;
    }
    dfs(son[u],x);
    en[u]=en[son[u]];
    for(int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v==fa[u]||v==son[u])continue;
        dfs(v,v);
        g[u][0]+=max(f[v][0],f[v][1]);
        g[u][1]+=f[v][0];
    }
}
//----------------------树剖 
void init(){
	dw.n=dw.m=2;
	dw.a[1][2]=dw.a[2][1]=-inf;
	for(int i=1;i<=n;i++){
		if(son[i]!=i){
			a[i].n=a[i].m=2;
			a[i].a[1][1]=a[i].a[2][1]=g[i][0];
			a[i].a[1][2]=g[i][1]+val[i];
			a[i].a[2][2]=-inf;
		}else{
			a[i]=dw;
		}
	}
}
jz get(int u){
	jz ans;
	ans.n=1,ans.m=2;
	ans.a[1][2]=val[en[u]];
	jz a=ask(1,n,1,dfn[u],dfn[en[u]]);
//	cout<<u<<" "<<dfn[u]<<" "<<dfn[en[u]]<<endl;
//	print(a);
	ans=ans*a;
	return ans;
}
void turnn(int x,int y){
	jz ol,ne;
	a[x].a[1][2]+=y-val[x];
	ol=get(top[x]);
	val[x]=y;	
	while(1){
		turn(1,n,1,dfn[x],a[x]);
		ne=get(top[x]);
		x=fa[top[x]];
		if(!x)return;
		int k=max(ne.a[1][1],ne.a[1][2])-max(ol.a[1][1],ol.a[1][2]);
		a[x].a[1][1]+=k;
		a[x].a[2][1]+=k;
		a[x].a[1][2]+=ne.a[1][1]-ol.a[1][1];
		ol=get(top[x]);
	}
}
void print(){
	for(int i=1;i<=n;i++)printf("f[%d][0]=%d,f[%d][1]=%d\n",i,f[i][0],i,f[i][1]);
	puts("");
	for(int i=1;i<=n;i++)printf("g[%d][0]=%d,g[%d][1]=%d\n",i,g[i][0],i,g[i][1]);
	puts("");
	for(int i=1;i<=n;i++)printf("son[%d]=%d\n",i,son[i]);
	puts("");
	for(int i=1;i<=n;i++)printf("nfd[%d]=%d\n",i,nfd[i]);
	puts("");
	for(int i=1;i<=n;i++){
		jz a=get(i);
		printf("f[%d][0]=%d,f[%d][1]=%d\n",i,a.a[1][1],i,a.a[1][2]);
	}
	puts("");
//	for(int i=1;i<=n;i++)printf("%d\n%d %d\n%d %d\n\n",i,a[i].a[1][1],a[i].a[1][2],a[i].a[2][1],a[i].a[2][2]);
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	//freopen("1.in","r",stdin);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>val[i];
	for(int i=1;i<n;i++){
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs1(1,0,1);
	dfs(1,1);
	init();
	build(1,n,1);
//	return 0;
	while(m--){
		cin>>x>>y;
		turnn(x,y);
		jz ans=get(1);
//		for(int i=1;i<=n;i++){
//			jz a=get(i);
//			printf("f[%d][0]=%d,f[%d][1]=%d\n",i,a.a[1][1],i,a.a[1][2]);
//		}
		cout<<max(ans.a[1][1],ans.a[1][2])<<endl;
	}
}