调了两天了求求了

#include<bits/stdc++.h>
#define Code using
#define by namespace
#define wjb std
Code by wjb;
int in()
{
	int k=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
	return k*f;
}
void out(int x)
{
	if(x<0)putchar('-'),x=-x;
	if(x<10)putchar(x+'0');
	else out(x/10),putchar(x%10+'0');
}
const int N=1e5+10,inf=1e9;
struct Matrix
{
	int r,c;
	vector<vector<int> >a;
	Matrix()
	{
		r=c=2;
		a=vector<vector<int> >(r,vector<int>(c));
		for(int i=0;i<r;i++)
			for(int j=0;j<c;j++)a[i][j]=-inf;
	}
	vector<int>& operator[](int i){return a[i];}
	const vector<int>& operator[](int i)const{return a[i];}
	Matrix operator*(const Matrix &b)const
	{
		Matrix ret;
		for(int i=0;i<r;i++)
			for(int j=0;j<b.c;j++)
				for(int k=0;k<c;k++)
					ret[i][j]=max(ret[i][j],a[i][k]+b[k][j]);
		return ret;
	}
};
#define lc (x<<1)
#define rc ((x<<1)|1)
struct nod
{
	int l,r;
	Matrix val;
};
int rnk[N];
Matrix val[N];
struct SEG
{
	nod tree[N<<2];
	void pushup(int x)
	{
		tree[x].val=tree[lc].val*tree[rc].val;
//		cout<<"pushup: "<<tree[x].val[0][1]<<" "<<tree[x].val[0][0]<<" "<<tree[x].val[1][0]<<"\n";
	}
	void build(int x,int l,int r)
	{
//		cout<<"build: "<<x<<" "<<l<<" "<<r<<"\n";
		tree[x].l=l,tree[x].r=r;
		if(l==r)
		{
			tree[x].val=val[rnk[l]];
			return;
		}
		int mid=(l+r)>>1;
		build(lc,l,mid),build(rc,mid+1,r);
		pushup(x);
	}
	void change(int x,int p)
	{
//		cout<<"change: "<<x<<"\n";
		if(tree[x].l==tree[x].r)
		{
			tree[x].val=val[rnk[p]];
			return;
		}
		int mid=(tree[x].l+tree[x].r)>>1;
		if(p<=mid)change(lc,p);
		else change(rc,p);
		pushup(x);
	}
	Matrix query(int x,int l,int r)
	{
//		cout<<"$$"<<l<<" "<<r<<endl;
		if(tree[x].l==l&&tree[x].r==r)return tree[x].val;
		int mid=(tree[x].l+tree[x].r)>>1;
		if(r<=mid)return query(lc,l,r);
		else if(l>mid)return query(rc,l,r);
		return query(lc,l,mid)*query(rc,mid+1,r);
	}
}T;
vector<int>e[N];
int son[N],siz[N],fa[N];
void build(int u)
{
	son[u]=-1,siz[u]=1;
	for(int v:e[u])
		if(v!=fa[u])
		{
			fa[v]=u;
			build(v);
			siz[u]+=siz[v];
			if(son[u]==-1||siz[v]>siz[son[u]])son[u]=v;
		}
}
int end1[N],top[N],dfn[N],cnt=0;
int f[N][5];
int a[N];
void cut(int u,int t)
{
//	cout<<"cut: u="<<u<<" t="<<t<<"\n";
	top[u]=t,dfn[u]=++cnt,rnk[cnt]=u,end1[t]=max(end1[t],cnt);
	f[u][0]=0,f[u][1]=a[u];
	val[u][0][0]=val[u][0][1]=0,val[u][1][0]=a[u];
//	cout<<"cut1: "<<val[u][0][0]<<" "<<val[u][0][1]<<" "<<val[u][1][0]<<endl;
	if(son[u]==-1)return;
	cut(son[u],t);
	f[u][0]+=max(f[son[u]][0],f[son[u]][1]);
	f[u][1]+=f[son[u]][0];
//	cout<<"out cut f: "<<f[u][0]<<" "<<f[u][1]<<endl;
	for(int v:e[u])
	{
		if(v==son[u]||v==fa[u])continue;
		cut(v,v);
		f[u][0]+=max(f[v][0],f[v][1]);
		f[u][1]+=f[v][0];
		val[u][0][0]+=max(f[v][0],f[v][1]);
		val[u][0][1]=val[u][0][0];
		val[u][1][0]+=f[v][0];
	}
//	cout<<"cut2: "<<val[u][0][0]<<" "<<val[u][0][1]<<" "<<val[u][1][0]<<endl;
}
void update(int u,int w)
{
	val[u][1][0]+=w-a[u],a[u]=w;
	Matrix nex,pre;
	while(u)
	{
		pre=T.query(1,dfn[top[u]],end1[top[u]]);
		T.change(1,dfn[u]);
		nex=T.query(1,dfn[top[u]],end1[top[u]]);
		u=fa[top[u]];
		val[u][0][0]+=max(nex[0][0],nex[1][0])-max(pre[0][0],pre[1][0]);
		val[u][0][1]=val[u][0][0];
		val[u][1][0]+=nex[0][0]-pre[0][0];
//		cout<<"update: "<<u<<"\n";
//		cout<<"val: "<<val[u][0][0]<<" "<<val[u][0][1]<<" "<<val[u][1][0]<<endl;
	}
}
void init(int s)
{
	build(s),cut(s,s);
}
int main()
{
//	freopen("in.txt","r",stdin);
//	freopen("f_ck.txt","w",stdout);
	int n=in(),m=in();
	for(int i=1;i<=n;i++)a[i]=in();
	for(int i=1;i<n;i++)
	{
		int u=in(),v=in();
		e[u].push_back(v),e[v].push_back(u);
	}
	init(1),T.build(1,1,n);
//	for(int i=1;i<=n;i++)cout<<"i: "<<dfn[i]<<" "<<end1[i]<<endl;
	while(m--)
	{
		int x=in(),w=in();
		update(x,w);
		Matrix ans=T.query(1,dfn[1],end1[1]);
		out(max(ans[0][0],ans[1][0])),putchar('\n');
	}
	return 0;
}