玄关求条

#include <bits/stdc++.h>

using namespace std;

const int N=200010;

int n,m,a[N],u,v,x,y,dfn[N],fan[N],son[N],dep[N],fa[N],siz[N],top[N],id,F[N][2],las[N];

vector<int> f[N]; 

struct jcd{
	int m[2][2];
	jcd(){memset(m,-0x3f,sizeof m);}
	jcd operator *(jcd b)const{
		jcd c;
		for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
		for(int k=0;k<2;k++)
		c.m[i][j]=max(c.m[i][j],m[i][k]+b.m[k][j]);
		return c;
	}
}g[N];

struct tr{
	int l[N<<2],r[N<<2];
	jcd ans[N<<2];
	void push(int p){
		ans[p]=ans[p<<1]*ans[p<<1|1];
	}
	void build(int p,int l1,int r1){
		l[p]=l1;r[p]=r1;
		if(l1==r1){
			ans[p]=g[fan[l[p]]];
			return ;
		}
		int mid=(l1+r1)>>1;
		build(p<<1,l1,mid);
		build(p<<1|1,mid+1,r1);
		push(p);
	}
	jcd query(int p,int l1,int r1){
//		cout<<p<<" "<<l[p]<<" "<<r[p]<<endl;
		if(l[p]==l1&&r[p]==r1){
			return ans[p];
		}
		int mid=(l[p]+r[p])>>1;
		if(l1>mid)return query(p<<1|1,l1,r1);
		else if(r1<=mid)return query(p<<1,l1,r1);
		else return query(p<<1|1,mid+1,r1)*query(p<<1,l1,mid);
	}
	
	void gai(int p,int k){
		if(l[p]==r[p]&&l[p]==k){
			ans[p]=g[fan[k]];
			return ;
		}
		int mid=(l[p]+r[p])>>1;
		if(k<=mid)gai(p<<1,k);
		else gai(p<<1|1,k);
		push(p); 
	}
}T;

void dfs(int p,int f1){
	dep[p]=dep[f1]+1;siz[p]=1;
	for(int op:f[p]){
		if(op==f1)continue;
		fa[op]=p;dfs(op,p);
		siz[p]+=siz[op];
		if(siz[son[p]]<siz[op])
		son[p]=op;
	}
}

void dfs1(int p,int tp){
	dfn[p]=++id;fan[id]=p;
	top[p]=tp;las[tp]=max(las[tp],id);
	F[p][0]=0;F[p][1]=a[p];
	g[p].m[0][0]=g[p].m[0][1]=0;
	g[p].m[1][0]=a[p];
	if(son[p]){
		dfs1(son[p],tp);
		F[p][0]+=max(F[son[p]][0],F[son[p]][1]);
		F[p][1]+=F[son[p]][0];
	}
	for(int op:f[p]){
		if(op==fa[p]||op==son[p])continue;
		dfs1(op,op);
		F[p][0]+=max(F[op][0],F[op][1]);
		F[p][1]+=F[op][0];
		g[p].m[0][0]+=max(F[op][0],F[op][1]);
		g[p].m[0][1]=g[p].m[0][0];
		g[p].m[1][0]+=F[op][0];
	}
}

void up(int p,int y){
	g[p].m[1][0]+=y-a[p];
	a[p]=y;jcd qian,hou;
	while(p){
//		cout<<p<<":"<<dfn[top[p]]<<" "<<las[top[p]]<<endl;
		qian=T.query(1,dfn[top[p]],las[top[p]]);
		T.gai(1,dfn[p]);
		hou=T.query(1,dfn[top[p]],las[top[p]]);
		p=fa[top[p]];
		g[p].m[0][0]+=max(hou.m[0][0],hou.m[1][0])-max(qian.m[0][0],qian.m[1][0]);
		g[p].m[0][1]=g[p].m[0][0];
		g[p].m[1][0]+=hou.m[0][0]-qian.m[0][0];
	}
	
}

void init(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	for(int i=1;i<n;i++){
		cin>>u>>v;
		f[u].push_back(v);
		f[v].push_back(u);
	}
	dfs(1,1);dfs1(1,1);
	T.build(1,1,n);
	jcd F1=T.query(1,dfn[1],las[1]);
	cout<<max(F1.m[0][0],F1.m[1][0])<<"\n";
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		up(x,y);
		jcd F1=T.query(1,dfn[1],las[1]);
		cout<<max(F1.m[0][0],F1.m[1][0])<<"\n";
	}
}

int main(){
	init();
	return 0;
}