事实上在小样例输入的时候这个程序的输出是一堆负无穷。

#include<bits/stdc++.h>
using namespace std;

const int N=100005,inf=0x3f3f3f3f;
int n,m,cnt,rnk[N],g[N][2],f[N][2];
vector<int>e[N];

struct matrix{
	int l1,l2,a[3][3];
	matrix(){
		l1=l2=2;
		a[1][1]=a[1][2]=a[2][1]=a[2][2]=-inf;
	}
};

matrix operator*(matrix a,matrix b){
	matrix c;
	c.l1=a.l1,c.l2=b.l2;
	for(int i=1;i<=c.l1;i++)
		for(int j=1;j<=c.l2;j++)
			for(int k=1;k<=a.l2;k++)
				c.a[i][j]=max(c.a[i][j],a.a[i][k]+b.a[k][j]);
	return c;
}

struct SegTree{
	int l,r;
	matrix mul;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define mul(x) tree[x].mul
}tree[N<<3];

struct node{
	int siz,fa,top,id,son,dep,val,bottom;
	node(){
		siz=fa=top=id=son=dep=val=bottom=0;
	}
}a[N];

void dfs1(int u,int f){
	a[u].fa=f;
	a[u].dep=a[f].dep+1;
	a[u].siz=1;
	int mx=0;
	for(int v:e[u]){
		if(v==f)continue;
		dfs1(v,u);
		a[u].siz+=a[v].siz;
		if(a[v].siz>mx){
			mx=a[v].siz;
			a[u].son=v;
		}
	}
}

void dfs2(int u,int f){
	a[u].top=f;
	a[u].id=++cnt;
	rnk[cnt]=u;
	if(!a[u].son)return a[u].bottom=u,void();
	dfs2(a[u].son,f);
	a[u].bottom=a[ a[u].son ].bottom;
	for(int v:e[u]){
		if(v==a[u].fa||v==a[u].son)continue;
		dfs2(v,v);
	}
}

void build(int u){
	g[u][1]=a[u].val;
	for(int v:e[u]){
		if(v==a[u].fa)continue;
		build(v);
		if(v==a[u].son)continue;
		g[u][1]+=f[v][0];
		g[u][0]+=max(f[v][1],f[v][0]);
	}
	f[u][1]=g[u][1]+f[ a[u].son ][0];
	f[u][0]=g[u][0]+max(f[ a[u].son ][0],f[ a[u].son ][1]);
	matrix ret;
	ret.a[1][1]=ret.a[1][2]=g[u][0];
	ret.a[2][1]=g[u][1];
	mul(a[u].id)=ret;
}

void pushup(int x){
	mul(x)=mul(x<<1)*mul(x<<1|1);
}

void build2(int x,int l,int r){
	l(x)=l,r(x)=r;
	if(l==r)return;
	int mid=l+r>>1;
	build2(x<<1,l,mid);
	build2(x<<1|1,mid+1,r);
	pushup(x);
}

void modify(int x,int pos){
	int l=l(x),r=r(x);
	if(l==r){
		int t=rnk[pos];
		mul(x).a[1][1]=mul(x).a[1][2]=g[t][0];
		mul(x).a[2][1]=g[t][1];
		return;
	}
	int mid=l+r>>1;
	if(pos<=mid)modify(x<<1,pos);
	else modify(x<<1|1,pos);
	pushup(x);
}

matrix query(int x,int askl,int askr){
	int l=l(x),r=r(x);
	if(askl>askr){
		matrix ret;
		ret.a[1][1]=ret.a[2][2]=0;
		return ret;
	}
	if(askl<=l&&r<=askr)
		return mul(x);
	int mid=l+r>>1;
	matrix ret;
	ret.a[1][1]=ret.a[2][2]=0;
	if(askl<=mid)ret=ret*query(x<<1,askl,askr);
	if(askr>mid)ret=ret*query(x<<1|1,askl,askr);
	return ret;
}

void change(int x,int val){
	g[x][1]+=val-a[x].val;
	a[x].val=val;
	modify(1,a[x].id);
	x=a[x].top;
	while(x!=1){
		matrix ret;
		ret.l2=1;
		ret.a[1][1]=0,ret.a[2][1]=a[ a[x].bottom ].val;
		ret=query(1,a[x].id,a[ a[x].bottom ].id-1)*ret;
		int fx0=f[x][0],fx1=f[x][1];
		f[x][0]=ret.a[1][1];
		f[x][1]=ret.a[2][1];
		g[ a[x].fa ][0]+=max(f[x][0],f[x][1])-max(fx0,fx1);
		g[ a[x].fa ][1]+=f[x][0]-fx0;
		modify(1,a[ a[x].fa ].id);
		x=a[ a[x].fa ].top;
	}
}

int fquery(int top){
	int bottom=a[top].bottom;
	matrix ret;
	ret.l2=1;
	ret.a[1][1]=0,ret.a[2][1]=a[bottom].val;
	if(a[bottom].id-1>=a[top].id)
		ret=query(1,a[top].id,a[bottom].id-1)*ret;
	return max(ret.a[1][1],ret.a[2][1]);
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i].val;
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1);
	build2(1,1,cnt);
	for(int i=1,u,v;i<=m;i++){
		cin>>u>>v;
		change(u,v);
		cout<<fquery(1)<<'\n';
	}
}