数据太大下载不了，不知道为什么卡不过去，其他的数据点跑的都挺快，麻烦高人指点。

下面这份代码因为卡常所以长得很丑，但是整体跟普通版的代码差不多。

#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int N=1000010,INF=0x3f3f3f3f;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline void swap(int &x,int &y){x^=y^=x^=y;}
int head[N],ver[N<<1],Next[N<<1],tot;
int n,m,lst,w[N],f[N],g[N],dp[N][2],sz[N],fa[N],top[N],son[N];
int st[N],rt[N],ls[N],rs[N],ff[N],sum[N],len[N];
namespace nqio{
const unsigned R=4e5,W=4e5;
char*a,*b,i[R],o[W],*c=o,*d=o+W,h[40],*p=h,y;
bool s;
struct q{
	__attribute__((always_inline))
	void r(char&x){x=a==b&&(b=(a=i)+fread(i,1,R,stdin),a==b)?-1:*a++;}
	void f(){fwrite(o,1,c-o,stdout);c=o;}
	~q(){f();}
	__attribute__((always_inline))
	void w(char x){*c=x;if(++c==d)f();}
	__attribute__((always_inline))
	q&operator>>(char&x){do r(x);while(x<=32);return*this;}
	__attribute__((always_inline))
	q&operator>>(char*x){do r(*x);while(*x<=32);while(*x>32)r(*++x);*x=0;return*this;}
	template<typename t>__attribute__((always_inline))
	q&operator>>(t&x){for(r(y),s=0;!isdigit(y);r(y))s|=y==45;if(s)for(x=0;isdigit(y);r(y))x=x*10-(y^48);else for(x=0;isdigit(y);r(y))x=x*10+(y^48);return*this;}
	__attribute__((always_inline))
	q&operator<<(char x){w(x);return*this;}
	q&operator<<(char*x){while(*x)w(*x++);return*this;}
	__attribute__((always_inline))
	q&operator<<(const char*x){while(*x)w(*x++);return*this;}
	template<typename t>__attribute__((always_inline))
	q&operator<<(t x){if(!x)w(48);else if(x<0)for(w(45);x;x/=10)*p++=48|-(x%10);else for(;x;x/=10)*p++=48|x%10;while(p!=h)w(*--p);return*this;}
}qio;
}
using nqio::qio;
struct matrix{
	int m00,m01,m10,m11;
	matrix operator *(const matrix &x)const{
		matrix c;
		c.m00=max(m00+x.m00,m01+x.m10);
		c.m01=max(m00+x.m01,m01+x.m11);
		c.m10=max(m10+x.m00,m11+x.m10);
		c.m11=max(m10+x.m01,m11+x.m11);
		return c;
	}
}tr[N<<2];
void add(int x,int y){
	ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
int build(int l,int r){
	if(l>r)return 0;
	int ql=l,qr=r,res=r;
	while(ql<=qr){
		int mid=(ql+qr)>>1;
		if(2*(sum[mid]-sum[ql-1])>=sum[qr]-sum[ql-1])qr=(res=mid)-1;
		else ql=mid+1;
	}
	int p=st[res];
	tr[p].m00=tr[p].m01=f[p];
	tr[p].m10=g[p];tr[p].m11=-INF;
	ls[p]=build(l,res-1);
	rs[p]=build(res+1,r);
	if(ls[p])tr[p]=tr[ls[p]]*tr[p],ff[ls[p]]=p;
	if(rs[p])tr[p]=tr[p]*tr[rs[p]],ff[rs[p]]=p;
	return p;
}
void dfs(int x){
	for(int i=x;i;i=son[i]){
		st[++len[x]]=i;top[i]=x;
		sum[len[x]]=sum[len[x]-1]+sz[i]-sz[son[i]];
	}
	rt[x]=build(1,len[x]);
	for(int i=x;i;i=son[i])
		for(int j=head[i];j;j=Next[j]){
			int y=ver[j];
			if(!top[y])dfs(y);
		}
}
void dfs(int x,int ffa){
	int cnt=0;
	sz[x]=1;fa[x]=ffa;
	dp[x][1]=g[x]=w[x];
	for(int i=head[x];i;i=Next[i]){
		int y=ver[i];
		if(y==ffa)continue;
		dfs(y,x);
		sz[x]+=sz[y];
		if(sz[y]>cnt)cnt=sz[y],son[x]=y;
		dp[x][0]+=max(dp[y][0],dp[y][1]);
		dp[x][1]+=dp[y][0];
	}
	for(int i=head[x];i;i=Next[i]){
		int y=ver[i];
		if(y!=ffa&&y!=son[x])f[x]+=max(dp[y][0],dp[y][1]),g[x]+=dp[y][0];
	}
}
void upd(int x){
	for(;x;x=ff[x]){
		tr[x].m00=tr[x].m01=f[x];
		tr[x].m10=g[x];tr[x].m11=-INF;
		if(ls[x])tr[x]=tr[ls[x]]*tr[x];
		if(rs[x])tr[x]=tr[x]*tr[rs[x]];
	}
}
void change(int x,int d){
	w[x]+=d,g[x]+=d;
	while(x){
		int ffa=fa[top[x]];
		if(ffa){
			matrix res=tr[rt[top[x]]];
			f[ffa]-=max(res.m00,res.m10);
			g[ffa]-=res.m00;
		}
		upd(x);
		if(ffa){
			matrix res=tr[rt[top[x]]];
			f[ffa]+=max(res.m00,res.m10);
			g[ffa]+=res.m00;
		}
		x=fa[top[x]];
	}
}
int main(){
	qio>>n>>m;
	for(int i=1;i<=n;i++)qio>>w[i];
	for(int i=1;i<n;i++){
		int x,y;
		qio>>x>>y;
		add(x,y),add(y,x);
	}
	dfs(1,0);dfs(1);
	while(m--){
		int x,d;
		qio>>x>>d;
		x^=lst;change(x,d-w[x]);
		lst=max(tr[rt[1]].m00,tr[rt[1]].m10);
		qio<<lst<<'\n';
	}
	return 0;
}