如题。 #2#4 TLE ，听说最卡的 #10 倒是过了。

#include<cstdio>
#include<cctype>
#include<algorithm>
const int maxn=1000010,inf=19260817;
int in(){
	int v=0,s=1;char c='~';
	while(!isdigit(c)){if(c=='-')s=-1;c=getchar();}
	while( isdigit(c)){v=(v<<3)+(v<<1)+(c^48);c=getchar();}
	return v*s;
}
struct grap{
	struct node{
		int n,t; 
	}dat[maxn<<1];
	int headx[maxn],tot;
	void add(const int x,const int y){
		dat[++tot]=(node){headx[x],y};
		headx[x]=tot;
	}
}gx;
inline int max(const int x,const int y){
	if(x>=y)return x;
	return y;
}
struct mtx{
	int f[2][2];
	mtx operator * (mtx x){
		mtx r;
		r.f[0][0]=max(x.f[0][0]+f[0][0],x.f[0][1]+f[1][0]);
		r.f[0][1]=max(x.f[0][0]+f[0][1],x.f[0][1]+f[1][1]);
		r.f[1][0]=max(x.f[1][0]+f[0][0],x.f[1][1]+f[1][0]);
		r.f[1][1]=max(x.f[1][0]+f[0][1],x.f[1][1]+f[1][1]);
		return r;
	}
	mtx(int A=0,int B=0,int C=0,int D=0){
		f[0][0]=A;f[1][0]=C;
		f[0][1]=B;f[1][1]=D;
	}
};
int s[maxn],sz[maxn],fa[maxn],top[maxn];
int szx[maxn],rt,c[maxn];
int f[maxn][2],g[maxn][2],ls[maxn],lsh;
struct FLCT{
	struct node{
		int s[2],f;
		mtx v,su;
	}d[maxn];
	#define l(x) d[x].s[0]
	#define r(x) d[x].s[1]
	#define f(x) d[x].f
	void pushup(const int x){
		d[x].su=d[l(x)].su*d[x].v*d[r(x)].su;
	}
}SF;
#define isrt(x) (SF.l(SF.f(x))!=x&&SF.r(SF.f(x))!=x)
int build(const int l,const int r,const int f){
	int tgt=(szx[l]+szx[r])>>1;
	if(l==r){
		SF.f(ls[l])=f;
		return ls[l];
	}
	int L=l,R=r,x=ls[l],mdx=l;
	while(L<=R){
		int mid=(L+R)>>1;
		if(sz[mid]>tgt){
			x=ls[mdx=mid];
			L=mid+1;
		}
		else R=mid-1;
	}
	SF.f(x)=f;
	if(mdx>l)SF.l(x)=build(l,mdx-1,x);
	if(mdx<r)SF.r(x)=build(mdx+1,r,x);
	SF.pushup(x);
	return x;
}
void dfs1(const int x,const int fax){
	sz[x]=1;fa[x]=fax;
	//f[x][1]=max()
	for(int i=gx.headx[x];i;i=gx.dat[i].n){
		int v=gx.dat[i].t;
		if(v==fax)continue;
		dfs1(v,x);
		sz[x]+=sz[v];
		if(sz[v]>sz[s[x]])s[x]=v;
	}
}
void dfs2(const int x,const int t){
	g[x][1]=c[x];g[x][0]=0;
	if(!s[x]){
		//end of a heavy list
		f[x][0]=g[x][0];f[x][1]=g[x][1];
		SF.d[x].v=mtx(g[x][0],g[x][1],-inf,-inf);
		SF.pushup(x);
		//return;
	}
	else {
		dfs2(s[x],t);
		for(int i=gx.headx[x];i;i=gx.dat[i].n){
			int v=gx.dat[i].t;
			if(v==fa[x]||s[x]==v)continue;
			dfs2(v,v);
			g[x][0]=g[x][0]+max(f[v][0],f[v][1]);
			g[x][1]=g[x][1]+f[v][0];
		}
		f[x][0]=g[x][0]+max(f[s[x]][0],f[s[x]][1]);
		f[x][1]=g[x][1]+f[s[x]][0];
		SF.d[x].v=mtx(g[x][0],g[x][1],g[x][0],-inf);
		SF.pushup(x);
	}
	if(x==t){
		//head of a list
		int top=0,y=x;
		while(y){
			ls[++top]=y;y=s[y];
			szx[top]=szx[top-1]+sz[x]-sz[s[x]];
		}
		rt=build(1,top,fa[t]);
		//1 is always the last to pop
	}
}
void modify(int x,const int v){
	g[x][1]=g[x][1]-c[x]+v;
	c[x]=v;
	SF.d[x].v=mtx(g[x][0],g[x][1],g[x][0],-inf);
	for(int i=x;i;i=SF.f(i)){
		if(isrt(i)&&SF.f(i)){
			int f=SF.f(i);
			g[f][0]-=max(SF.d[i].su.f[0][0],SF.d[i].su.f[0][1]);
			g[f][1]-=SF.d[i].su.f[0][0];
			SF.pushup(i);
			g[f][0]+=max(SF.d[i].su.f[0][0],SF.d[i].su.f[0][1]);
			g[f][1]+=SF.d[i].su.f[0][0];
			SF.d[f].v=mtx(g[f][0],g[f][1],g[f][0],-inf);
		}
		else{
			SF.pushup(i);
		}
	}
}
int main(){
	SF.d[0].v=mtx(0,-inf,-inf,0);
	SF.d[0].su=mtx(0,-inf,-inf,0);
	int n=in(),T=in();
	for(int i=1;i<=n;i++)c[i]=in();
	for(int i=1;i< n;i++){
		int x=in(),y=in();
		gx.add(x,y);gx.add(y,x);
	}
	int root=32424654685ll%n+1;
	dfs1(root,0);
	dfs2(root,root);
	int la=0;
	while(T--){
		int x=in()^la,y=in();
		modify(x,y);
		printf("%d\n",la=max(SF.d[rt].su.f[0][0],SF.d[rt].su.f[0][1]));
	}
	return 0;
}