动态DP

https://www.cnblogs.com/RabbitHu/p/9112811.html
$f[i][1]$f[i][1]为选点$i$i的最大权独立集。
$f[i][0]$f[i][0]为不选$i$i的最大权独立集。
$g[u][0]$g[u][0]为轻儿子都不选的最大值。
$g[u][1]$g[u][1]为轻儿子可以选的最大值
$\begin{bmatrix}f[v][0],f[v][1]\end{bmatrix} \times \begin{bmatrix}g[u][1]&g[u][0]+val[u]\\g[u][1]& -\infty\end{bmatrix}=\begin{bmatrix}f[u][0],f[u][1]\end{bmatrix}$[f[v][0],f[v][1]​]×[g[u][1]g[u][1]​g[u][0]+val[u]−∞​]=[f[u][0],f[u][1]​]
然后乘法换为+，加法换为取max。
LCT日常维护，$g$g为虚子树，求链上不满足交换律的积。
AC Code:

#include<bits/stdc++.h>
#define maxn 100005
#define inf 0x3f3f3f3f
using namespace std;

int n,m,val[maxn];
struct mat{
	int a[2][2];
	mat (int d=0){a[0][0]=a[1][1]=d,a[0][1]=a[1][0]=-inf;}
	mat operator *(const mat &B)const{
		mat ret(-inf);
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				for(int k=0;k<2;k++)
					ret.a[i][k] = max(ret.a[i][k] , a[i][j] + B.a[j][k]);
		return ret;
	}
};
namespace LCT{
	int ch[maxn][2],fa[maxn];
	mat g[maxn],s[maxn];
	#define il inline 
	#define pa fa[x]
	il int inr(int x){ return ch[pa][1]==x; }
	il int isr(int x){ return ch[pa][0]!=x&&ch[pa][1]!=x; }
	il void upd(int x){
		s[x] = s[ch[x][1]] * g[x] * s[ch[x][0]];
	}
	il void rot(int x){
		int y=fa[x],z=fa[y],c=inr(x);
		if(!isr(y)) ch[z][inr(y)]=x;
		(ch[y][c]=ch[x][!c])&&(fa[ch[y][c]]=y);
		fa[fa[ch[x][!c]=y]=x]=z;
		upd(y);
	}
	il void splay(int x){
		for(;!isr(x);rot(x))
			if(!isr(pa)) rot(inr(pa)==inr(x)?pa:x); 
		upd(x);
	}
	il int access(int x,int y=0){
		for(;x;x=fa[y=x]){
			splay(x);
			if(ch[x][1]){
				int a0 = max(s[ch[x][1]].a[0][0],s[ch[x][1]].a[1][0]),
					a1 = max(s[ch[x][1]].a[0][1],s[ch[x][1]].a[1][1]);
				g[x].a[0][0] += max(a0,a1);
				g[x].a[1][0] += max(a0,a1);
				g[x].a[0][1] += a0;
			}
			if(y){
				int a0 = max(s[y].a[0][0],s[y].a[1][0]),
					a1 = max(s[y].a[0][1],s[y].a[1][1]);
				g[x].a[0][0] -= max(a0,a1);
				g[x].a[1][0] -= max(a0,a1);
				g[x].a[0][1] -= a0;
			}
			ch[x][1] = y , upd(x);
		}
		return y;
	}
}
using namespace LCT;
int info[maxn],Prev[maxn<<1],to[maxn<<1],cnt_e;
void Node(int u,int v){ Prev[++cnt_e]=info[u],info[u]=cnt_e,to[cnt_e]=v; }

void dfs(int now,int ff){
	fa[now] = ff , g[now].a[0][0] = 0 , 
	g[now].a[0][1] = val[now] , g[now].a[1][0] = 0 , g[now].a[1][1] = -inf;
	for(int i=info[now];i;i=Prev[i])
		if(to[i]!=ff){
			dfs(to[i],now);
			int a0 = max(s[to[i]].a[0][0],s[to[i]].a[1][0]),
				a1 = max(s[to[i]].a[0][1],s[to[i]].a[1][1]);
			g[now].a[0][0] += max(a0,a1);
			g[now].a[1][0] += max(a0,a1);
			g[now].a[0][1] += a0;
		}
	upd(now);
	/*printf("%d\n",now);
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			printf("s[%d][%d] = %d\n",i,j,s[now].a[i][j]);*/
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&val[i]);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		Node(u,v),Node(v,u);
	}
	dfs(1,0);
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		access(x),splay(x);
		g[x].a[0][1] += y - val[x];
		val[x] = y;
		upd(x);
		printf("%d\n",max(max(s[x].a[0][0],s[x].a[0][1]),max(s[x].a[1][0],s[x].a[1][1])));
	}
}