【专题】动态DP

因为想把$NOIP2018$NOIP2018的保卫王国切掉，所以开了这个天坑…
emmm，似乎能加深我对矩阵和动态树的理解的亚子？
管他的，冲了

1. 【模板】动态 DP
   真不是我说，带了修改瞬间黄题到黑题
   讲一下我的麻瓜理解吧
   先考虑一条链的情况（定理：一条链能做，那么树上就能做我现编的 ）
   暴力很好想，想不出来的我估计也不会来看这篇文章
   简单放一下柿子
   $dp[i][0]=max(dp[i+1][0],dp[i+1][1])$dp[i][0]=max(dp[i+1][0],dp[i+1][1])
   $dp[i][1]=dp[i+1][0]+val[i]$dp[i][1]=dp[i+1][0]+val[i]
   那么考虑如何快速解决修改问题
   首先需要会矩阵这个鬼东西
   我们可以把上述柿子改成一个矩阵
   可以用
   $\begin{matrix} 0 &0 \\ val[i] & -inf \\ \end{matrix} \tag{1}$0val[i]​0−inf​(1)
   来"乘"上
   $\begin{matrix} dp[i+1][0] \\ dp[i+1][1] \\ \end{matrix} \tag{1}$dp[i+1][0]dp[i+1][1]​(1)
   当然不是真的乘啦
   自己体会一下其实是我不会写公式
   那么我们就可以用线段树来维护一段区间矩阵的乘积
   改的时候直接$log(n)$log(n)暴力改
   算的时候直接大力区间的乘积就好
   推广到树上，树剖/$LCT$LCT维护一波就好
   上$LCT$LCT代码

#include<bits/stdc++.h>
#define il inline
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1e5+5;
int N,M,val[maxn];
vector<int>G[maxn];
struct Martix{
	int A[3][3];
//	Martix(){
//		memset(A,0x8f,sizeof(A));
//	}
	il void Init(int a,int b){
		A[1][1]=A[1][2]=a;
		A[2][1]=b;
		A[2][2]=-INF;
	}
	friend Martix operator *(Martix a,Martix b){
		Martix c;
		for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
			c.A[i][j]=max(a.A[i][1]+b.A[1][j],a.A[i][2]+b.A[2][j]);
		return c;
	}
};
struct LCT{
	int fa[maxn],ch[maxn][2],dp[maxn][2];
	Martix martix[maxn];
	il bool Check(int x){
		return x==ch[fa[x]][1];
	}
	il bool Root(int x){
		return x!=ch[fa[x]][0]&&x!=ch[fa[x]][1];
	}
	il void Update(int x){
		martix[x].Init(dp[x][0],dp[x][1]);
		if(ch[x][0])
			martix[x]=martix[ch[x][0]]*martix[x];
		if(ch[x][1])
			martix[x]=martix[x]*martix[ch[x][1]];
	}
	il void Rotate(int x){
		int y=fa[x],z=fa[y],k=Check(x),w=ch[x][k^1];
		if(!Root(y))ch[z][Check(y)]=x;fa[x]=z;
		ch[x][k^1]=y;fa[y]=x;
		ch[y][k]=w;fa[w]=y;
		Update(y);Update(x);
	}
	il void Splay(int x){
		while(!Root(x)){
			int y=fa[x];
			if(!Root(y)){
				if(Check(x)==Check(y))
					Rotate(y);
				else
					Rotate(x);
			}
			Rotate(x);
		}
	}
	il void Access(int x){
		for(int i=0;x;i=x,x=fa[x]){
			Splay(x);
			if(ch[x][1]){
				dp[x][0]+=max(martix[ch[x][1]].A[1][1],martix[ch[x][1]].A[2][1]);
				dp[x][1]+=martix[ch[x][1]].A[1][1];
			}
			if(i){
				dp[x][0]-=max(martix[i].A[1][1],martix[i].A[2][1]);
				dp[x][1]-=martix[i].A[1][1];
			}
			ch[x][1]=i;
			Update(x);
		}
	}
	il void Dfs(int u,int p){
		dp[u][0]=0;
		dp[u][1]=val[u];
		fa[u]=p;
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i];
			if(v==p)
				continue;
			Dfs(v,u);
			dp[u][0]+=max(dp[v][1],dp[v][0]);
			dp[u][1]+=dp[v][0];
		}
		martix[u].Init(dp[u][0],dp[u][1]);
	}
}T;
int main(){
	//freopen("in.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin>>N>>M;
	for(int i=1;i<=N;i++)
		cin>>val[i];
	for(int i=1,u,v;i<N;i++){
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	T.Dfs(1,0);
	for(int i=1,a,b;i<=M;i++){
		cin>>a>>b;
		T.Access(a);
		T.Splay(a);
		T.dp[a][1]+=b-val[a];
		val[a]=b;
		T.Update(a);
		T.Splay(1);
		cout<<max(T.martix[1].A[1][1],T.martix[1].A[2][1])<<endl;
	}
	return 0;
}