死了。没什么好说的

#include<bits/stdc++.h>
#define N 100500
#define inf 0x3f3f3f3f
using namespace std;
int n,q,val[N],u,v,node,up;

struct Edge{int to;int next;}edge[N<<1];
int head[N],cnt;
inline void add(int u,int v){
	edge[++cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
}

inline int max(int x,int y){return x>y?x:y;}
struct matrix{
	int a[2][2];
	matrix operator * (matrix x){
		matrix temp;
		temp.a[0][0]=max(a[0][0]+x.a[0][0],a[0][1]+x.a[1][0]);
		temp.a[0][1]=max(a[0][0]+x.a[0][1],a[0][1]+x.a[1][1]);
		temp.a[1][0]=max(a[1][0]+x.a[0][0],a[1][1]+x.a[1][0]);
        temp.a[1][1]=-inf;
		//temp.a[1][1]=max(a[1][0]+x.a[0][1],a[1][1]+x.a[1][1]);
		return temp;
	}
}f[N],s[N];

int size[N],son[N],fa[N],dep[N],bot[N];
int top[N],id[N],oid[N],ID;
void dfs1(int x,int father)
{
	size[x]=1; fa[x]=father;
	dep[x]=dep[father]+1; //son[x]=0;
	for(int i=head[x];i;i=edge[i].next)
		if(edge[i].to!=father)
		{
			dfs1(edge[i].to,x);
			size[x]+=size[edge[i].to];
			if(size[edge[i].to]>size[son[x]])	son[x]=edge[i].to;
		}
	bot[x]=son[x]?bot[son[x]]:x;
}
void dfs2(int x,int topx)
{
	id[x]=++ID;	oid[ID]=x;	top[x]=topx;
	if(!son[x]){f[x].a[1][0]=val[x];return;}
	s[x].a[1][0]=val[x];
	dfs2(son[x],topx);
	for(int i=head[x];i;i=edge[i].next)
		if(edge[i].to!=fa[x]&&edge[i].to!=son[x])
		{
			dfs2(edge[i].to,edge[i].to);
			s[x].a[0][0]+=max(f[edge[i].to].a[0][0],f[edge[i].to].a[1][0]);
			s[x].a[0][1]+=max(f[edge[i].to].a[0][0],f[edge[i].to].a[1][0]);
			//s[x].a[0][0]=(s[x].a[0][1]+=max(f[edge[i].to].a[0][0],f[edge[i].to].a[1][0]));
			s[x].a[1][0]+=f[edge[i].to].a[0][0];
		}
	f[x].a[0][0]=s[x].a[0][0]+max(f[son[x]].a[0][0],f[son[x]].a[1][0]);
	f[x].a[1][0]=s[x].a[1][0]+f[son[x]].a[0][0];
}

matrix tree[N<<2],V;int L,R,X;
inline void pushup(int rt){tree[rt]=tree[rt<<1]*tree[rt<<1|1];}
void build(int l,int r,int rt)
{
	if(l==r){tree[rt]=s[l];	return;}
	int mid=(l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	pushup(rt);
}
void update(int l,int r,int rt)
{
	if(l==r){tree[rt]=V;return;}
	int mid=(l+r)>>1;
	if(X<=mid)	update(l,mid,rt<<1);
	else	update(mid+1,r,rt<<1|1);
	pushup(rt);
}
matrix query(int l,int r,int rt)
{
	if(L<=l&&r<=R)	return tree[rt];
	//if(l>R||r<L)	return empty;if(L<=mid&&mid<r)
	int mid=(l+r)>>1;
    if(R<=mid)  return query(l,mid,rt<<1);
    if(mid<L)   return query(mid+1,r,rt<<1|1);
    return query(l,mid,rt<<1)*query(mid+1,r,rt<<1|1);
}
void solve(int x)
{
    //L=R=id[x];  temp=query(1,n,1);
	s[x].a[1][0]+=up-val[x];    val[x]=up;
	while(x)
	{
		X=id[x]; V=s[x]; update(1,n,1);
		L=id[top[x]],R=id[fa[bot[x]]];//R=id[bot[x]];//
		V=query(1,n,1)*f[bot[x]];
        x=top[x];
		//s[x=top[x]]=V;
		//temp=s[fa[x]];
 		s[fa[x]].a[0][0]+=max(V.a[0][0],V.a[1][0])-max(f[x].a[0][0],f[x].a[1][0]);
		s[fa[x]].a[0][1]+=max(V.a[0][0],V.a[1][0])-max(f[x].a[0][0],f[x].a[1][0]);
		s[fa[x]].a[1][0]+=V.a[0][0]-f[x].a[0][0];
        //s[fa[x]].a[1][1]=-inf;
		f[x]=V; x=fa[x];
	}
}

int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)	scanf("%d",&val[i]),s[i].a[1][1]=-inf;
	for(int i=1;i<n;i++)	scanf("%d%d",&u,&v),add(u,v),add(v,u);
	dfs1(1,0);	dfs2(1,1);
	build(1,n,1);
	//return 0;
	while(q--)
	{
		scanf("%d%d",&node,&up);    solve(node);
		printf("%d\n",max(f[1].a[0][0],f[1].a[1][0]));
	}
}