C++ :

#include<bits/stdc++.h>
using namespace std;
#define N 400010
const int BUF=12324865;
char Buf[BUF],*buf=Buf;
template<class T>inline void rd(T &a){
	for (a=0;*buf<48;buf++);
	while (*buf>47) a=(a<<1)+(a<<3)+((*buf++)^48);
}
struct edge{
	int nxt,t;
}e[N<<1];
int head[N],edge_cnt;
void add_edge(int x,int y){
	e[edge_cnt]=(edge){head[x],y};
	head[x]=edge_cnt++;
}
long long Ans;
struct Link_Cut_Tree{
	#define Lc son[now][0]
	#define Rc son[now][1]
	int son[N][2],fa[N],stk[N];
	long long val[N],sum[N],vsum[N];
	bool is_Rt(int x){
		return son[fa[x]][0]!=x && son[fa[x]][1]!=x;
	}
	void Up(int now){
		sum[now]=val[now]+sum[Lc]+sum[Rc]+vsum[now];
	}
	void Rotate(int now){
		int pre=fa[now];
		int P=fa[pre];
		int f=(son[pre][0]==now);
		bool Rt=is_Rt(pre);
		
		fa[now]=P;
		fa[pre]=now;
		fa[son[now][f]]=pre;
		
		if (!Rt) son[P][son[P][1]==pre]=now;
		son[pre][!f]=son[now][f];
		son[now][f]=pre;
		
		Up(pre);
	}
	void Splay(int now){
		while (!is_Rt(now)){
			int pre=fa[now];
			if (!is_Rt(pre)){
				if ((son[fa[pre]][0]==pre)^(son[pre][0]==now)) Rotate(now);
				else Rotate(pre);
			}
			Rotate(now);
		}
		Up(now);
	}
	void Access(int now,int w,int Nxt){
		for (;now;Nxt=now,now=fa[now]){
			Splay(now);
			long long Sum=sum[Rc]+val[now]+vsum[now];
			if (Rc) Ans-=2*(Sum-sum[Rc]);
			else if (Sum+1<=val[now]*2) Ans-=2*(Sum-val[now]);
			else Ans-=Sum-1;
			sum[now]+=w;
			vsum[now]+=w;
			Sum+=w;
			if (Sum+1>sum[Rc]*2){
				vsum[now]+=sum[Rc];
				Rc=0;
			}
			if (Sum+1<=sum[Nxt]*2){
				Rc=Nxt;
				vsum[now]-=sum[Rc];
			}
			if (Rc) Ans+=2*(Sum-sum[Rc]);
			else if (Sum+1<=val[now]*2) Ans+=2*(Sum-val[now]);
			else Ans+=Sum-1;
		}
	}
	void Update(int now,int w){
		Splay(now);
		long long Sum=sum[Rc]+val[now]+vsum[now];
		if (Rc) Ans-=2*(Sum-sum[Rc]);
		else if (Sum+1<=val[now]*2) Ans-=2*(Sum-val[now]);
		else Ans-=Sum-1;
		val[now]+=w;
		sum[now]+=w;
		Sum+=w;
		if (Sum+1>sum[Rc]*2){
			vsum[now]+=sum[Rc];
			Rc=0;
		}
		if (Rc) Ans+=2*(Sum-sum[Rc]);
		else if (Sum+1<=val[now]*2) Ans+=2*(Sum-val[now]);
		else Ans+=Sum-1;
		Access(fa[now],w,now);
	}
	void dfs(int x,int f){
		fa[x]=f;
		sum[x]=val[x];
		int i,p=x;
		long long Mx=val[x];
		for (i=head[x];~i;i=e[i].nxt){
			int to=e[i].t;
			if (to==f) continue;
			dfs(to,x);
			sum[x]+=sum[to];
			if (sum[to]>Mx){
				p=to;
				Mx=sum[to];
			}
		}
		Ans+=min(sum[x]-1,2*(sum[x]-Mx));
		if (p!=x && sum[x]+1<=Mx*2) son[x][1]=p;
		vsum[x]=sum[x]-val[x]-sum[son[x][1]];
	}
	void build(){
		dfs(1,0);
	}
}LCT;
int main(){
	memset(head,-1,sizeof(head));
	fread(Buf,1,BUF,stdin);
	int n,m,i;
	rd(n),rd(m);
	for (i=1;i<=n;i++) rd(LCT.val[i]);
	for (i=1;i<n;i++){
		int x,y;
		rd(x),rd(y);
		add_edge(x,y);
		add_edge(y,x);
	}
	LCT.build();
	printf("%lld\n",Ans);
	for (i=1;i<=m;i++){
		int x,w;
		rd(x),rd(w);
		LCT.Update(x,w);
		printf("%lld\n",Ans);
	}
	return 0;
}