#include<bits/stdc++.h>
#define gc IO::fastgc()
#define pc(c)IO::fastpc(c)
typedef long long ll;typedef long long unsigned llu,ull;typedef long double lf;
using namespace std;
namespace IO{char ibuf[1<<23],obuf[1<<23],*ip1=ibuf,*ip2=ibuf,*o=obuf;inline char fastgc(){return((ip1==ip2)&&(ip2=(ip1=ibuf)+fread(ibuf,1,1<<21,stdin),ip1==ip2)?EOF:*ip1++);}inline void fastpc(char c){(o-obuf<(1<<22))?(*(o++)=c):(fwrite(obuf,o-obuf,1,stdout),o=obuf,*(o++)=c);}struct _{_(){}~_(){fwrite(obuf,o-obuf,1,stdout);}}__;}template<typename T>inline void read(T&t){t=0;T f=1;char c=gc;while(c!='-'&&(c<'0'||c>'9')){c=gc;}if(c=='-'){f=-1,c=gc;}while(c>='0'&&c<='9'){t=10*t+(c&15),c=gc;}t*=f;}template<>inline void read<string>(string&t){t="";char c=gc;while(isspace(c)||c==EOF){c=gc;}while(!(isspace(c)||c==EOF)){t+=c,c=gc;}}template<typename T>inline void write(T x){if(!x){return(void)pc('0');}if(x<0){pc('-'),x=-x;}static char c[33]={""};static int cc=0;while(x){c[++cc]=x%10,x/=10;}while(cc){pc(c[cc--]|48);}}inline void write(const string&x){for(auto c:x){pc(c);}}inline void write(const char*x){for(;*x;++x){pc(*x);}}inline void write(char _){pc(_);}template<typename T1,typename...Args>inline void read(T1&v1,Args&...args){read(v1),read(args...);}template<typename T1,typename...Args>inline void write(const T1&v1,const Args&...args){write(v1),write(args...);}
constexpr unsigned N=1e5+7,M=2e5+17,NN=4e5+37;
int n,m,a[N];
int ec,eh[N],nxt[M],to[M];
int dft,sz[N],fa[N],dep[N],dfn[N],pos[N],hs[N],tp[N],ed[N];
int f[N][2],g[N][2];
struct Matrix {
	static constexpr unsigned N=2;
	int n,m,a[N][N];
	inline void zero() {
		n=m=0;
		for(unsigned i {0}; i<N; ++i)for(unsigned j {0}; j<N; ++j) {
				a[i][j]=-0x3F3F3F3F;
			}
	}
	inline void unit(unsigned _) {
		n=m=_;
		for(unsigned i {0}; i<_; ++i)for(unsigned j {0}; j<_; ++j) {
				a[i][j]=(i==j)?0:(-0x3F3F3F3F);
			}
	}
	inline int*operator[](unsigned _) {
		return a[_];
	}
	inline const int*operator[](unsigned _)const {
		return a[_];
	}
	inline Matrix operator*(const Matrix&b)const {
		Matrix c;
		c.zero();
		c.n=n,c.m=b.m;
		for(int k {0}; k<m; ++k)for(int i {0}; i<n; ++i)for(int j {0}; j<b.m; ++j) {
					c[i][j]=max(c[i][j],a[i][k]+b[k][j]);
				}
		return c;
	}
};
inline void out(const Matrix&x){
	printf("[%d,%d,%d,%d]\n",x[0][0],x[0][1],x[1][0],x[1][1]);
}
namespace Seg{
	struct SegNode {
		int l,r;
		Matrix f;
	} tr[NN];
	inline void init(int k,int u){
		tr[k].f.zero(),tr[k].f.n=tr[k].f.m=2;
		tr[k].f[0][0]=tr[k].f[0][1]=g[u][0],tr[k].f[1][0]=g[u][1];
	}
	inline void pushup(int k){
		tr[k].f=tr[k<<1].f*tr[k<<1|1].f;
	}
	void build(int k,int l,int r){
		tr[k].l=l,tr[k].r=r;
		if(l==r) {
			init(k,pos[l]);
			return;
		}
		int m {(l+r)>>1};
		build(k<<1,l,m),build(k<<1|1,m+1,r),pushup(k);
	}
	void modify(int k,int x){
		if(tr[k].l>x||tr[k].r<x) {
			return;
		}
		if(tr[k].l==tr[k].r) {
			return init(k,pos[x]);
		}
		modify(k<<1,x),modify(k<<1|1,x);
		pushup(k);
	}
	Matrix query(int k,int l,int r){
		Matrix ret;
		ret.unit(2);
		if(tr[k].l>r||tr[k].r<l) {
			return ret;
		}
		if(tr[k].l>=l&&tr[k].r<=r) {
			return tr[k].f;
		}
		int m {(l+r)>>1};
		if(r<=m) {
			return query(k<<1,l,r);
		} else if(l>=m+1) {
			return query(k<<1|1,l,r);
		} else {
			return query(k<<1,l,r)*query(k<<1|1,l,r);
		}
	}
};
inline void _adde(int u,int v){
	nxt[++ec]=eh[u],to[ec]=v,eh[u]=ec;
}
inline void adde(int u,int v){
	_adde(u,v),_adde(v,u);
}
void dfs1(int u,int fa){
	::fa[u]=fa,dep[u]=dep[fa]+1,sz[u]=1;
	for(int i {eh[u]}; i; i=nxt[i]) {
		int v {to[i]};
		if(v==fa) {
			continue;
		}
		dfs1(v,u);
		sz[u]+=sz[v];
		if(!hs[u]||sz[v]>sz[hs[u]]) {
			hs[u]=v;
		}
	}
}
void dfs2(int u,int fa,int tpn){
	pos[dfn[u]=++dft]=u,tp[u]=tpn,ed[tpn]=max(ed[tpn],dft);
	if(hs[u]) {
		dfs2(hs[u],u,tpn);
	}
	for(int i {eh[u]}; i; i=nxt[i]) {
		int v {to[i]};
		if(v==fa||v==hs[u]) {
			continue;
		}
		dfs2(v,u,v);
	}
}
void dfs3(int u,int fa){
	f[u][0]=g[u][0]=0,f[u][1]=g[u][1]=a[u];
	if(hs[u]) {
		dfs3(hs[u],u);
		f[u][0]+=max(f[hs[u]][0],f[hs[u]][1]);
		f[u][1]+=f[hs[u]][0];
	}
	for(int i {eh[u]}; i; i=nxt[i]) {
		int v {to[i]};
		if(v==fa||v==hs[u]) {
			continue;
		}
		dfs3(v,u);
		f[u][0]+=max(f[v][0],f[v][1]);
		f[u][1]+=f[v][0];
		g[u][0]+=max(f[v][0],f[v][1]);
		g[u][1]+=f[v][0];
	}
}
inline void modify(int x,int v){
	g[x][1]+=(v-a[x]);
	a[x]=v;
	Matrix lst,tmp;
	while(x) {
		lst=Seg::query(1,dfn[tp[x]],ed[tp[x]]);
		Seg::modify(1,dfn[x]);
		tmp=Seg::query(1,dfn[tp[x]],ed[tp[x]]);
		x=fa[tp[x]];
		g[x][0]+=max(tmp[0][0],tmp[1][0])-max(lst[0][0],lst[1][0]);
		g[x][1]+=tmp[0][0]-lst[0][0];
	}
}
inline int query(){
	auto f=Seg::query(1,dfn[1],ed[1]);
	Matrix ret;
	ret.zero();
	ret.n=ret.m=2;
	ret[0][0]=ret[0][1]=0;
	ret=f;
	return max(ret[0][0],ret[1][0]);
}
signed main(){
	read(n,m);
	for(int i {1}; i<=n; ++i) {
		read(a[i]);
	}
	for(int i {1}; i<n; ++i) {
		int u,v;
		read(u,v);
		adde(u,v);
	}
	dfs1(1,0),dfs2(1,0,1),dfs3(1,0),
	Seg::build(1,1,dft);
	while(m--) {
		int x,y;
		read(x,y);
		modify(x,y);
		write(query(),'\n');
	}
	return 0;
}