#include<bits/stdc++.h>
#include<unistd.h>
using namespace std;
#define For(i, l, r) for(int i=(l);i<=(r);++i)
#define Rfor(i, r, l) for(int i=(r);i>=(l);--i)
#define O(x) cerr<<#x<<":"<<x<<endl
#define OO(x,y) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<endl
#define OOO(x,y,z) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl
#define OOOO(x,y,z,f) cerr<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<(#z)<<":"<<(z)<<" "<<(#f)<<":"<<f<<endl
#define LO(a, l, r) For(supervariable, l, r)cerr<<a[supervariable]<<" ";cerr<<"\n"
#define FS(v,V,u,fa) for(int v:V[(u)])if(v!=(fa))
#define FENGE cerr<<"----------------------------------------------------------"<<endl
int read(){int x=0,t=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')t=-t;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return x*t;}
int buf[1<<20];
void write(int x,char ch='\n')
{
	if(x==0){putchar('0'),putchar(ch);return;}
	buf[0]=0;while(x)buf[++buf[0]]=x%10,x/=10;
	Rfor(i, buf[0], 1)putchar(buf[i]+'0');
	putchar(ch);
}
const int N=1000005;
int a[N],n;
vector<int> V[N];
namespace C
{
	int fa[N],siz[N],bel[N],top[N],bottom[N],num,dfn[N],out[N],seq[N],son[N];
	void advanced(int x,int fat)
	{
		siz[x]=1;fa[x]=fat;
		FS(v,V,x,fat)advanced(v,x),siz[x]+=siz[v],siz[v]>siz[son[x]]&&(son[x]=v);
	}
	void build(int x,bool New)
	{
		seq[dfn[x]=++dfn[0]]=x;
		if(New)top[bel[x]=++num]=x;else bel[x]=num;
		if(!son[x]){bottom[bel[x]]=x;goto End;}
		build(son[x],0);
		FS(v,V,x,fa[x])if(v!=son[x])build(v,1);
		End:;out[x]=dfn[0];
	}
}
namespace F
{
	int g[N][2],f[N][2];
	void advanced(int x)
	{
		f[x][1]=a[x];
		FS(v,V,x,C::fa[x])
			if(v!=C::son[x])advanced(v),f[x][0]+=max(f[v][0],f[v][1]),f[x][1]+=f[v][0];
		if(!C::son[x])return;
		g[x][0]=f[x][0];g[x][1]=f[x][1]; advanced(C::son[x]);f[x][0]+=max(f[C::son[x]][0],f[C::son[x]][1]);f[x][1]+=f[C::son[x]][0];
	}
}
namespace T
{
	int dinf=-1e8;
	struct V
	{
		int v[2];
		V(){}
		V(int x,int y) : v{x,y} {}
	};
	struct M
	{
		int m[2][2]={{0,dinf},{dinf,0}};
		M operator*(M x)
		{
			M res;
			res.m[0][0]=max(m[0][0]+x.m[0][0],m[0][1]+x.m[1][0]);
			res.m[0][1]=max(m[0][0]+x.m[0][1],m[0][1]+x.m[1][1]);
			res.m[1][0]=max(m[1][0]+x.m[0][0],x.m[1][0]+m[1][1]);
			res.m[1][1]=max(m[1][1]+x.m[1][1],m[1][0]+x.m[0][1]);
			return res;
		}
		V operator*(V x){V res; res.v[0]=max(m[0][0]+x.v[0], m[0][1]+x.v[1]); res.v[1]=max(m[1][0]+x.v[0], m[1][1]+x.v[1]); return res;}
	}G[N];
	struct NODE{int son[2],l,r,mid;M val;}tr[N<<1];int cnt;

	void pushUp(int x){tr[x].val=tr[tr[x].son[0]].val*G[tr[x].mid]*tr[tr[x].son[1]].val;}
	void make(int x,int l){int u=C::seq[l];tr[x].val.m[0][0]=F::g[u][0];tr[x].val.m[0][1]=F::g[u][0];tr[x].val.m[1][0]=F::g[u][1];tr[x].val.m[1][1]=dinf;return;}
	void makeG(int x){int u=C::seq[x];G[x].m[0][0]=F::g[u][0];G[x].m[0][1]=F::g[u][0];G[x].m[1][0]=F::g[u][1];G[x].m[1][1]=dinf;}
	
	int pre[N];	
	int Find(int x,int dep)
	{
		For(i, tr[x].l, tr[x].r)
			if(pre[i]*2>=pre[tr[x].r])return i;
	}
	void build(int &x,int l,int r,int dep)
	{
		if(l>r){x=0;return;}
		x=++cnt;tr[x].l=l;tr[x].r=r;
		if(l==r){make(x,l);return;}
		tr[x].mid=Find(x,dep);
		build(tr[x].son[0],l,tr[x].mid-1,dep^1);build(tr[x].son[1],tr[x].mid+1,r,dep^1);
		pushUp(x);
	}
	int rt[N];
	void advanced()
	{
		For(i, 1, n)makeG(i);
		For(i, 1, C::num)
		{
			pre[C::dfn[C::top[i]]-1]=0;
			For(j, C::dfn[C::top[i]], C::dfn[C::bottom[i]])pre[j] = pre[j-1] + C::siz[C::seq[j]] - C::siz[C::son[C::seq[j]]];
			build(rt[i], C::dfn[C::top[i]], C::dfn[C::bottom[i]], 0);
		}
	}
	void update(int x,int idx)
	{
		if(tr[x].l==tr[x].r){make(x,tr[x].l);return;}
		int mid=tr[x].mid;
		if(idx<mid)update(tr[x].son[0],idx);
		if(idx>mid)update(tr[x].son[1],idx);
		pushUp(x);
	}
	M query(int x,int L,int R)
	{
		if(!x)return tr[0].val;
		if(L<=tr[x].l&&R>=tr[x].r)return tr[x].val;
		int mid=tr[x].mid;M res;
		if(L<mid)res=res*query(tr[x].son[0],L,R);
		if(L<=mid&&R>=mid)res=res*G[tr[x].mid];
		if(R>mid)res=res*query(tr[x].son[1],L,R);
		return res;
	}
}
namespace C
{
	T::V query(int x)
	{
		T::V tmp(0, a[bottom[bel[x]]]);tmp=T::query(T::rt[bel[x]], dfn[x], dfn[bottom[bel[x]]]-1)*tmp;
		return tmp;
	}
	void update(int x,int val)
	{
		F::g[x][1]+=val-a[x];a[x]=val;T::makeG(dfn[x]);T::update(T::rt[bel[x]], dfn[x]);//O("!");
		T::V tmp(F::f[x][0],F::f[x][1]);
		while(x)
		{
			int t=top[bel[x]];T::V tmp=query(t);
			x=fa[top[bel[x]]];
			if(x){F::g[x][0]+=max(tmp.v[0],tmp.v[1])-max(F::f[t][0],F::f[t][1]);F::g[x][1]+=tmp.v[0]-F::f[t][0];T::makeG(dfn[x]);T::update(T::rt[bel[x]], dfn[x]);}
			F::f[t][0]=tmp.v[0];F::f[t][1]=tmp.v[1];
		}
		
	}
}
int main()
{
	n=read();int m=read();
	For(i, 1, n)a[i]=read();
	For(i, 1, n-1){int x=read(),y=read();V[x].emplace_back(y);V[y].emplace_back(x);}
	C::advanced(1, 0);C::build(1, 1);F::advanced(1);T::advanced();
	int lastans=0;
	For(i, 1, m)
	{
		int x=read()^lastans,y=read();
		C::update(x,y);
		write(lastans=max(F::f[1][0],F::f[1][1]));
	}
}