动态dp
前置知识
广义矩阵乘法
一般矩阵乘法在dp转移时难以使用，于是，我们可以定义一个更方便应用于dp的矩阵乘法（下面为区分计为\(*\)）
定义矩阵A，B
\[A*B=\begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix}*\begin{bmatrix} b_1 & b_2 \\ b_3 & b_4 \end{bmatrix}=\begin{bmatrix} max(a_1+b_1,a_2+b_3) & max(a_1+b_2,a_2+b_4) \\ max(a_3+b_1,a_4+b_3) & max(a_3+b_2,a_4+b_4) \end{bmatrix}
\]
不难发现，\(*\)就是在原矩阵乘法的基础上将乘改为了取最大值，它仍然满足结合律（具体为什么自己证明）
树链剖分
重链剖分容易被卡，建议学习全局平衡二叉树(我不会)
解题
题目链接
首先，这个题目要求求最大权独立集，直接考虑树上dp，就是P1352转移方程为
\[f_{x,1}=a_x+ \sum f_{y,0}
\]
\[f_{x,0}=\sum max(f_{y,0},f_{y,1})
\]
但是我们这里带修改，如果再跑一遍时间一定会超，于是我们考虑用矩阵加速。但是我们带\(\sum\)的转移难以使用矩阵乘法，于是我们考虑改一下转移方程。如果将树剖成链，那么我们就可以将转移方程改为
\[f_{x,1}=f_{son_x,0}+g_{x,1}
\]
\[\begin{aligned}
f_{x,0}&=max(f_{son_x,0},f_{son_x,1})+g_{x,0}\\
&=max(f_{son_x,0}+g_{x,0},f_{son_x,1}+g_{x,0})\end{aligned}
\]
其中，\(g\)表示只考虑轻儿子时的\(f\)，然后我们就可以把上述方程改为一个\(*\)式子
\[\begin{bmatrix}f_{x,0} \\ f_{x,1} \end{bmatrix}=\begin{bmatrix} g_{x,0} & g_{x,0} \\ g_{x,1} & -\infty \end{bmatrix}*\begin{bmatrix} f_{y,0} \\ f_{y,1} \end{bmatrix}
\]
然后\(*\)满足结合律，还在链上连续，于是我们很容易就能想到使用线段树维护区间乘来得到每个链的dp数组了
代码：
using namespace std;
//#define int long long
#define endl '\n'
const int N=1e5+5;
int n,m;
int num,b[N*2],p[N],nt[N*2];
void add(int x,int y)
{++num;b[num]=y;nt[num]=p[x];p[x]=num;
}
struct Matrix
{int m[5][5];Matrix(){memset(m,-0x3F,sizeof(m));}
};
Matrix operator * (Matrix &A,Matrix &B)
{Matrix 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],A.m[i][k]+B.m[k][j]);return C;
}
//广义矩阵乘法
int f[N][2],a[N];
//f[i][1]表示选择i号点时，以i号点为根的子树的最大权独立集
//f[i][0]表示不选择i号点时，以i号点为根的子树的最大权独立集
Matrix val[N];//点的转移矩阵，用原序存
/*
g放在了矩阵中
g[i][1]表示i号点只考虑轻儿子的取自己的最大权独立集
g[i][0]表示i号点的所有轻儿子，可取可不取形成的最大权独立集
即g只处理轻儿子部分
因此，我们可以得到以下转移方程：
f[i][1]=g[i][1]+f[j][0]
f[i][0]=g[i][0]+max(f[j][0],f[j][1])
转移就可以当做一个广义矩阵乘
|g[i][0] g[i][0]| |f[j][0]| |max(g[i][0]+f[j][0],g[i][0]+f[j][1])| |g[i][0]+max(f[j][0],f[j][1])| |f[i][0]|
|g[i][1] -inf | * |f[j][1]| = |max(g[i][1]+f[j][0],-inf) | = |g[i][1]+f[j][0] | = |f[j][0]|
于是就可以通过用线段树维护链上的区间乘来维护链的dp矩阵
*///树链剖分
int fa[N],siz[N],dep[N],son[N],top[N],dfn[N],id[N],cnt,ed[N];
void dfs1(int x)
{siz[x]=1;for(int i=p[x];i;i=nt[i]){int y=b[i];if(y==fa[x])continue;fa[y]=x;dep[y]=dep[x]+1;dfs1(y);siz[x]+=siz[y];if(siz[y]>siz[son[x]])son[x]=y;}
}
void dfs2(int x,int t)
{top[x]=t;dfn[x]=++cnt;id[cnt]=x;ed[t]=max(ed[t],cnt);//当前链链头对应的链尾f[x][0]=0;f[x][1]=a[x];//叶子节点直接赋值f[x][0]=0,f[x][1]为x的权值val[x].m[0][0]=val[x].m[0][1]=0;val[x].m[1][0]=a[x];/*|0 0 | |g[x][0] g[x][0]||a[x] -inf|这个矩阵对应|g[x][1] -inf |*/if(!son[x])return;dfs2(son[x],t);f[x][0]+=max(f[son[x]][0],f[son[x]][1]);f[x][1]+=f[son[x]][0];//重儿子的转移不计入g数组for(int i=p[x];i;i=nt[i]){int y=b[i];if(y==fa[x]||y==son[x])continue;dfs2(y,y);f[x][0]+=max(f[y][0],f[y][1]);f[x][1]+=f[y][0];val[x].m[0][0]+=max(f[y][0],f[y][1]);val[x].m[0][1]=val[x].m[0][0];val[x].m[1][0]+=f[y][0];}
}//树剖完后链上用线段树处理区间矩阵乘
struct node
{int l,r;Matrix M;
}tr[N*4];
void pushup(int p){tr[p].M=tr[p*2].M*tr[p*2+1].M;}
void build(int l,int r,int p)
{tr[p].l=l;tr[p].r=r;if(l==r){tr[p].M=val[id[l]];//直接赋值return;}int mid=(l+r)/2;build(l,mid,p*2);build(mid+1,r,p*2+1);pushup(p);//处理矩阵
}
void update(int p,int x)//线段树单点修改
{if(tr[p].l==tr[p].r){tr[p].M=val[id[x]];return;}int mid=(tr[p].l+tr[p].r)/2;if(x<=mid)update(p*2,x);else update(p*2+1,x);pushup(p);
}
Matrix query(int l,int r,int p)
{if(tr[p].l==l&&tr[p].r==r)return tr[p].M;int mid=(tr[p].l+tr[p].r)/2;if(mid>=r)return query(l,r,p*2);else if(mid<l)return query(l,r,p*2+1);else {Matrix A=query(l,mid,p*2),B=query(mid+1,r,p*2+1);return A*B;}
}
void updatepa(int x,int w)//点权修改
{val[x].m[1][0]+=w-a[x];//修改转移矩阵左下角a[x]=w;Matrix bef,aft;//bef为原链的转移矩阵，aft为修改后链的转移矩阵while(x!=0)//从当前点出发向上修改链{bef=query(dfn[top[x]],ed[top[x]],1);update(1,dfn[x]);aft=query(dfn[top[x]],ed[top[x]],1);x=fa[top[x]];//更新val[x].m[0][0]+=max(aft.m[0][0],aft.m[1][0])-max(bef.m[0][0],bef.m[1][0]);val[x].m[0][1]=val[x].m[0][0];val[x].m[1][0]+=aft.m[0][0]-bef.m[0][0];}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<n;i++){int x,y;cin>>x>>y;add(x,y);add(y,x);}dfs1(1);dfs2(1,1);build(1,n,1);for(int i=1;i<=m;i++){int x,y;cin>>x>>y;updatepa(x,y);Matrix ans=query(dfn[1],ed[1],1);cout<<max(ans.m[0][0],ans.m[1][0])<<endl;}
}