是动态dp的板子

大致思想就是用g[u]来表示不包含重链转移的dp值，然后用线段树维护重链，这样线段树的根就相当于这条重链的top的真实dp值

每次修改的时候，修改x点会影响到x到根的真实dp值，但是只会影响到每条重链的低端点的dp值，相当于在log个线段树上单点修改

#include<iostream>

#include<cstdio>

using namespace std;

const int N=200005;

int n,m,a[N],h[N],cnt,de[N],fa[N],si[N],hs[N],fr[N],la[N],id[N],rl[N],tot,f[N][2],g[N][2],rt[N];

struct qwe

{

	int ne,to;

}e[N<<1];

struct jz

{

	int a[2][2];

	jz operator * (const jz &b) const

	{

		jz c;

		c.a[0][0]=c.a[0][1]=c.a[1][0]=c.a[1][1]=0;

		for(int i=0;i<2;i++)

			for(int j=0;j<2;j++)

				for(int k=0;k<2;k++)

					c.a[i][j]=max(c.a[i][j],a[i][k]+b.a[k][j]);

		return c;

	}

};

struct xds

{

	int l,r,ls,rs;

	jz v;

}t[N<<2];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void add(int u,int v)

{

	cnt++;

	e[cnt].ne=h[u];

	e[cnt].to=v;

	h[u]=cnt;

}

void dfs1(int u,int fat)

{

	fa[u]=fat;

	de[u]=de[fat]+1;

	si[u]=1;

	for(int i=h[u];i;i=e[i].ne)

		if(e[i].to!=fat)

		{

			dfs1(e[i].to,u);

			si[u]+=si[e[i].to];

			if(si[e[i].to]>si[hs[u]])

				hs[u]=e[i].to;

		}

}

void dfs2(int u,int top)

{

	fr[u]=top;

	la[top]=u;

	id[u]=++tot;

	rl[tot]=u;

	if(!hs[u])

		return;

	dfs2(hs[u],top);

	for(int i=h[u];i;i=e[i].ne)

		if(e[i].to!=fa[u]&&e[i].to!=hs[u])

			dfs2(e[i].to,e[i].to);

}

void dfs(int u,int fa)

{

	f[u][1]=g[u][1]=a[u];

	for(int i=h[u];i;i=e[i].ne)

		if(e[i].to!=fa)

		{

			dfs(e[i].to,u);

			f[u][0]+=max(f[e[i].to][0],f[e[i].to][1]),f[u][1]+=f[e[i].to][0];

			if(e[i].to!=hs[u])

				g[u][0]+=max(f[e[i].to][0],f[e[i].to][1]),g[u][1]+=f[e[i].to][0];

		}

}

void build(int &ro,int l,int r,int u)

{

	ro=++tot;

	t[ro].l=l,t[ro].r=r;

	if(l==r)

	{

		t[ro].v.a[0][0]=t[ro].v.a[0][1]=g[rl[id[u]+l-1]][0];

		t[ro].v.a[1][0]=g[rl[id[u]+l-1]][1],t[ro].v.a[1][1]=0;

		return;

	}

	int mid=(l+r)>>1;

	build(t[ro].ls,l,mid,u);

	build(t[ro].rs,mid+1,r,u);

	t[ro].v=t[t[ro].ls].v*t[t[ro].rs].v;

}

void update(int ro,int p,int u)

{

	if(t[ro].l==t[ro].r)

	{

		t[ro].v.a[0][0]=t[ro].v.a[0][1]=g[u][0];

		t[ro].v.a[1][0]=g[u][1],t[ro].v.a[1][1]=0;

		return;

	}

	int mid=(t[ro].l+t[ro].r)>>1;

	if(p<=mid)

		update(t[ro].ls,p,u);

	else

		update(t[ro].rs,p,u);

	t[ro].v=t[t[ro].ls].v*t[t[ro].rs].v;

}

void gai(int x,int y)

{

	g[x][1]+=y;

	while(x)

	{

		jz a=t[rt[fr[x]]].v,b;

		update(rt[fr[x]],de[x]-de[fr[x]]+1,x);

		b=t[rt[fr[x]]].v;

		x=fa[fr[x]];

		g[x][0]+=max(b.a[0][0],b.a[1][0])-max(a.a[0][0],a.a[1][0]);

		g[x][1]+=b.a[0][0]-a.a[0][0];

	}

}

int main()

{

	n=read(),m=read();

	for(int i=1;i<=n;i++)

		a[i]=read();

	for(int i=1;i<n;i++)

	{

		int x=read(),y=read();

		add(x,y),add(y,x);

	}

	dfs1(1,0);

	dfs2(1,1);

	dfs(1,0);

	tot=0;

	for(int i=1;i<=n;i++)

		if(i==fr[i])

			build(rt[i],1,de[la[i]]-de[i]+1,i);

	while(m--)

	{

		int x=read(),y=read();

		gai(x,y-a[x]);

		a[x]=y;

		printf("%d\n",max(t[rt[1]].v.a[0][0],t[rt[1]].v.a[1][0]));

	}

	return 0;

}