准备退役 whk 了，最后学点东西。
不得不承认，CSPS2022 T4 对动态 DP 起到了良好的普及效果。
P4719 【模板】"动态 DP"&动态树分治
设 \(f_{u,0/1}\) 表示不选/选 \(u\)，\(u\) 的子树内的最大权独立集。
不带修改的情况，有
\[f_{u,0}=\sum\max(f_{v,0},f_{v,1}) \]\[f_{u,1}=val_u+\sum f_{v,0} \]答案即为 \(\max(f_{1,0},f_{1,1})\)。
如果带修改呢？修改的结点影响的仅是其到根节点的路径。可以用树剖（重链剖分），为啥？
树剖有很好的性质：重儿子的 \(dfs\) 序连续，任意节点到根节点最多经过 \(\log n\) 条轻边。
这启示我们可以把轻儿子的信息合并起来，对于重儿子在跳重链的时候合并。
设 \(g_{u,0/1}\) 表示只考虑轻儿子，且 \(u\) 不选/选的最大权独立集。则有
\[f_{u,0}=g_{u,0}+\max(f_{son_u,0},f_{son_u,1}) \]\[f_{u,1}=g_{u,1}+f_{son_u,0} \]\(son_u\) 表示 \(u\) 的重儿子。这样我们还把 \(\sum\) 去掉了。
现在的问题就是如何快速合并和修改了，注意到可以使用广义矩阵乘法实现，有
\[f_{u,0}=\max(g_{u,0}+f_{son_u,0},g_{u,0}+f_{son_u,1}) \]\[f_{u,1}=\max(g_{u,1}+f_{son_u,0},-\infty) \]即
\[\begin{bmatrix}g_{i,0}&g_{i,0}\\g_{i,1}&-\infty\end{bmatrix}\begin{bmatrix}f_{son_u,0}\\f_{son_u,1}\end{bmatrix}=\begin{bmatrix}f_{u,0}\\f_{u,1}\end{bmatrix} \]注意这里矩阵一定得这么写，因为链头在区间左端，链尾在区间右端，维护的初始信息在叶子结点，所以只能把它放在右边。
怎么合并？废话，重链直接合并，向上跳轻边的时候合并到上一级重链，修改的时候用增量的方式改变父亲代表的矩阵。
点击查看代码
#define pb push_back
const int N=1e5+10,inf=0x3f3f3f3f;
int n,m;
vector<int> e[N];
int siz[N],fa[N],son[N],in[N],out[N],top[N],rnk[N],tim=0;
int f[N][2],a[N];
struct matrix{
int m[2][2];
inline matrix operator *(const matrix& b)const{
matrix res;
res.m[0][0]=res.m[0][1]=res.m[1][0]=res.m[1][1]=-inf;
for(int k=0;k<2;++k){
for(int i=0;i<2;++i){
for(int j=0;j<2;++j){
res.m[i][j]=max(res.m[i][j],m[i][k]+b.m[k][j]);
}
}
}return res;
}
}val[N],mat[N<<2],bef,aft;
void dfs1(int u,int f){
fa[u]=f,siz[u]=1;
for(int v:e[u])if(v!=f){
dfs1(v,u);siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void dfs2(int u,int t){//预处理出初始矩阵
top[u]=t,rnk[in[u]=++tim]=u,out[t]=max(out[t],tim);
//out 表示链顶所在链的链底
f[u][0]=0,f[u][1]=a[u];
val[u].m[0][0]=val[u].m[0][1]=0;
val[u].m[1][0]=a[u];val[u].m[1][1]=-inf;
if(son[u]){
dfs2(son[u],t);//重儿子不用算到 g 里面
f[u][0]+=max(f[son[u]][0],f[son[u]][1]);
f[u][1]+=f[son[u]][0];
}
for(int v:e[u])if(v!=fa[u]&&v!=son[u]){
dfs2(v,v);
f[u][0]+=max(f[v][0],f[v][1]);
f[u][1]+=f[v][0];
val[u].m[0][0]+=max(f[v][0],f[v][1]);
val[u].m[0][1]=val[u].m[0][0];
val[u].m[1][0]+=f[v][0];
}
}
#define ls p<<1
#define rs p<<1|1
void build(int p,int l,int r){
if(l==r)return mat[p]=val[rnk[l]],void();
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
mat[p]=mat[ls]*mat[rs];
}
void modify(int p,int l,int r,int pos){
if(l==r)return mat[p]=val[rnk[pos]],void();
int mid=(l+r)>>1;
if(pos<=mid)modify(ls,l,mid,pos);
else modify(rs,mid+1,r,pos);
mat[p]=mat[ls]*mat[rs];
}
matrix query(int p,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return mat[p];
int mid=(l+r)>>1;
if(qr<=mid)return query(ls,l,mid,ql,qr);
if(ql>mid)return query(rs,mid+1,r,ql,qr);
return query(ls,l,mid,ql,mid)*query(rs,mid+1,r,mid+1,qr);
}
void change(int u,int k){
val[u].m[1][0]+=k-a[u];a[u]=k;
while(u){
bef=query(1,1,n,in[top[u]],out[top[u]]);
modify(1,1,n,in[u]);
aft=query(1,1,n,in[top[u]],out[top[u]]);
u=fa[top[u]];
//向上跳轻边用增量法修改，注意矩阵中的元素代表的意义以及转移式
val[u].m[0][0]+=max(aft.m[0][0],aft.m[1][0])-max(bef.m[0][0],bef.m[1][0]);
val[u].m[0][1]=val[u].m[0][0];
val[u].m[1][0]+=aft.m[0][0]-bef.m[0][0];
}
}
int main(){
read(n),read(m);
for(int i=1;i<=n;++i)read(a[i]);
for(int i=1,u,v;i<n;++i){
read(u),read(v);
e[u].pb(v),e[v].pb(u);
}dfs1(1,0),dfs2(1,1);build(1,1,n);
for(int i=1,x,y;i<=m;++i){
read(x),read(y);
change(x,y);
matrix ans=query(1,1,n,in[1],out[1]);
printf("%d\n",max(ans.m[0][0],ans.m[1][0]));
}
return 0;
}
其他例题以后再补吧。
标签：val,int,max,top,mid,son,动态,DP From： https://www.cnblogs.com/RuntimeErr/p/16857065.html