RT

没过后三个样例。

调出来预处理三个dfs没错。

dp 的数组什么都没问题。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define mid (l+r>>1)
#define ls x<<1,l,mid
#define rs x<<1|1,mid+1,r
inline int read(){
	register int x=0,f=0,ch=getchar();
	while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
	return f?-x:x;
}
const int MAX=1e5+5;
int n,m;
struct Mat{
	int a[3][3];
	Mat(){memset(a,-0x3f,sizeof(a));}
	inline Mat operator * (Mat S){
		Mat T;
		for(register int i=1;i<=2;++i)
			for(register int j=1;j<=2;++j)
				for(register int k=1;k<=2;++k)
					T.a[i][j]=max(T.a[i][j],a[i][k]+S.a[k][j]);
		return T;
	}
}tree[MAX<<2],val[MAX],ans,A,B;
int w[MAX],b,c;
int siz[MAX],son[MAX],id[MAX],idx,dfn[MAX],top[MAX],end[MAX],fa[MAX];// 树剖的数组 
int f[MAX][2],g[MAX][2];// dp 数组 

struct E{int e,next;}e[MAX<<1];int tot=1,head[MAX];
inline void add(int u,int v){e[tot]=(E){v,head[u]};head[u]=tot++;}

inline void pushup(int x){tree[x]=tree[x<<1]*tree[x<<1|1];}
void build(int x,int l,int r){
	if(l==r){
		val[dfn[l]].a[1][1]=val[dfn[l]].a[1][2]=g[dfn[l]][0];
		val[dfn[l]].a[2][1]=g[dfn[l]][1];
		tree[x]=val[dfn[l]]; 
		return ;
	}
	build(ls);build(rs);pushup(x);
}
void modify(int x,int l,int r,int s){
	if(l==r){tree[x]=val[dfn[s]];return ;}
	if(s<=mid)modify(ls,s);else modify(rs,s);
	pushup(x);
}
Mat query(int x,int l,int r,int s,int t){
	if(s<=l&&r<=t)return tree[x];
	if(s<=mid)return query(ls,s,t);
	else if(mid<t)return query(rs,s,t);
	else return query(ls,s,t)*query(rs,s,t);
} 

void dfs1(int x,int f){
	fa[x]=f;siz[x]=1;
	for(register int i=head[x];i;i=e[i].next){
		if(e[i].e!=f){
			dfs1(e[i].e,x);siz[x]+=siz[e[i].e];
			if(siz[e[i].e]>siz[son[x]])son[x]=e[i].e;
		}
	}
}
void dfs2(int x,int t){
	top[x]=t;id[x]=++idx;dfn[idx]=x;end[t]=idx;
	if(son[x])dfs2(son[x],t);
	for(register int i=head[x];i;i=e[i].next){
		if(e[i].e!=fa[x]&&e[i].e!=son[x])dfs2(e[i].e,e[i].e);
	} 
}
void dfs3(int x){
	g[x][1]=w[x];
	for(register int i=head[x];i;i=e[i].next){
		if(e[i].e!=fa[x]&&e[i].e!=son[x]){
			dfs3(e[i].e);
			g[x][0]+=max(f[e[i].e][0],f[e[i].e][1]);
			g[x][1]+=f[e[i].e][0]; 
		}
	}
	f[x][0]+=g[x][0];f[x][1]+=g[x][1];
	if(son[x]){
		dfs3(son[x]);
		f[x][0]+=max(f[son[x]][0],f[son[x]][1]);
		f[x][1]+=f[son[x]][0]; 
	}
}

inline void Tmodify(int x,int y){
	val[x].a[2][1]+=y-w[x];w[x]=y;
	while(x!=0){
		B=query(1,1,n,id[top[x]],end[top[x]]);
		modify(1,1,n,id[x]);
		A=query(1,1,n,id[top[x]],end[top[x]]);
		x=fa[top[x]];
		val[x].a[1][1]+=max(A.a[1][1],A.a[2][1])-max(B.a[1][1],B.a[2][1]);
		val[x].a[1][2]=val[x].a[1][1];
		val[x].a[2][1]+=A.a[1][1]-B.a[1][1];
	}
}
signed main(){
	n=read(),m=read();
	for(register int i=1;i<=n;++i)w[i]=read();
	for(register int i=1;i<n;++i){
		b=read(),c=read();
		add(b,c),add(c,b);
	}
	dfs1(1,0);dfs2(1,1);dfs3(1);build(1,1,n);
	while(m--){
		b=read(),c=read();Tmodify(b,c);
		ans=query(1,1,n,id[1],end[1]);
		printf("%d\n",max(ans.a[1][1],ans.a[2][1]));
	}
	return 0;
}