先放code，末尾是能炸出来错误的数据，第二次询问答案234实际输出238。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+1,inf=INT_MAX-1;
struct gv
{
	int x,y;
	inline gv operator *(const gv& a) const
	{
		gv r;r.x=max(a.x,a.y)+x,r.y=y+a.x;
		return r;
	}
};
int fa[N],dfn[N],dep[N],top[N],siz[N],hs[N],id[N],v[N],ed[N],dfc,n;
struct sgt
{
	struct xds
	{
		int ls,rs;int l,r;
		gv v;
	}nds[N*40];int ct,rt;
	gv g[N]; 
	#define ls(x) (nds[x].ls)
	#define rs(x) (nds[x].rs)
	inline void up(int x)
	{
		nds[x].v=nds[ls(x)].v*nds[rs(x)].v;
	}
	void cons(int &x,int l,int r)
	{
		if(!x) x=++ct;
		nds[x].l=l,nds[x].r=r;
		if(l==r)
		{
			nds[x].v=g[id[l]];return;
		}
		auto mid=(l+r)/2;
		cons(ls(x),l,mid);cons(rs(x),mid+1,r);up(x);
	}
	void change(int x,int l,int r,int q)
	{
		if(l==r)
		{
			nds[x].v=g[id[l]];return;
		}
		auto mid=(l+r)/2;
		if(q<=mid) change(ls(x),l,mid,q);
		else change(rs(x),mid+1,r,q);up(x);
	}
	gv qdp(int x,int L,int R)
	{
		assert(x);
		if(L<=nds[x].l&&nds[x].r<=R) return nds[x].v;
		auto mid=(nds[x].l+nds[x].r)/2;
		if(R<=mid) return qdp(ls(x),L,R);
		if(L>mid) return qdp(rs(x),L,R);
		return qdp(ls(x),L,R)*qdp(rs(x),L,R);
	}
	inline void upgrade(int x,int val)
	{
		g[x].y+=val-v[x];
		v[x]=val;
		while(x)
		{
			gv inm=qdp(rt,dfn[top[x]],ed[top[x]]);
			change(rt,1,n,dfn[x]);
			gv TON=qdp(rt,dfn[top[x]],ed[top[x]]);
			x=fa[top[x]];//if(!x) continue;
			g[x].x+=max(TON.x,TON.y)-max(inm.x,inm.y);
			g[x].y+=TON.x-inm.x;
		}
	}
};
sgt YJSNPI;
int m;
struct edge
{
	int t,nt;
}G[N<<1];int hentai[N],baka;
inline void add_edge(int u,int v)
{
	G[++baka]=edge{v,hentai[u]},hentai[u]=baka;
}
#define H(x) (hentai[x])
#define RAPE(u) for(int i=H(u);i;i=G[i].nt) 
int urusai[N][2];
int dfs1(int u,int f,int d)
{
	dep[u]=d,fa[u]=f,siz[u]=1;auto mx=0;urusai[u][1]=v[u];
	RAPE(u) if(G[i].t^f)
	{
		int v=G[i].t;siz[u]+=dfs1(v,u,d+1);
		if(mx<siz[v]) mx=siz[v],hs[u]=v;
		urusai[u][1]+=urusai[v][0];
		urusai[u][0]+=max(urusai[v][0],urusai[v][1]);
	}
	return siz[u];
}
void dfs2(int u,int t)
{
	top[u]=t,dfn[u]=++dfc,id[dfc]=u,ed[t]=dfc;
	YJSNPI.g[u]=gv{0,v[u]};
	if(!hs[u]) return;
	dfs2(hs[u],t);
	RAPE(u) if((G[i].t^fa[u])&&(G[i].t^hs[u]))
	{
		auto v=G[i].t;dfs2(v,v);
		YJSNPI.g[u].y+=urusai[v][0],
		YJSNPI.g[u].x+=max(urusai[v][0],urusai[v][1]);
	}
}
int main()
{
	cin>>n>>m;
	for(auto i=1;i<=n;++i) cin>>v[i];
	for(auto i=1;i<=n-1;++i)
	{
		auto u=0,v=0;cin>>u>>v;add_edge(u,v),add_edge(v,u);
	}
	dfs1(1,0,1),dfs2(1,1);YJSNPI.cons(YJSNPI.rt,1,n);
	for(auto i=1;i<=m;++i)
	{
		int x,val;cin>>x>>val;
		YJSNPI.upgrade(x,val);
		gv ans=YJSNPI.qdp(YJSNPI.rt,1,ed[1]);
		cout<<max(ans.x,ans.y)<<endl;
	}
	return 0;
}/*
10 2
-11 80 -99 -76 56 38 92 -51 -34 47 
2 1
3 1
4 3
5 2
6 2
7 1
8 2
9 4
10 7
2 98
8 48
*/

实现时直接维护了转移的结合结果而非矩乘，但应该不是这里的原因，另一版用矩乘写错得一模一样。

目测线段树或者更新出锅，树剖部分好像没问题，但只是好像。