动态dp学习笔记
yokai_ing
·
·
个人记录
动态dp
主要是动态维护树上的dp值，此题为动态最大独立集。
- 经典的分轻重儿子把递推式优化为方便维护矩阵修改的形式。
- 这广义矩阵乘法用处挺大，还能用来在线段树上维护递推式来着，才知道递推能这么优化来维护。
首先，静态最大独立集方程是:
\begin{cases}
f_{i,0}=\sum_{son}{\max(f_{son_i,0},f_{son_i,1})}\\
f_{i,1}=\sum_{son} f_{son_i,0}+v_i;
\end{cases}
\end{equation}
把他拆为方便剖分更新的形式，即轻重儿子分开处理，多设一个g_i为在不考虑重儿子情况下的f数组，f的转移也要变，应由g配上重儿子转来，这样方便修改，修改为：
\begin{cases}
f_{i,0}=g_{i,0}+\max(f_{son,0},f_{son,1});\\
f_{i,1}=g_{i,1}+f_{son,0};
\end{cases}
\end{equation}
注意到重儿子贡献被独立出来了。
所以构造广义转移矩阵，剖分构造线段树维护矩乘，再暴力修改每次只需从修改节点往上跳到根节点，暴力改每条重链链头的父亲节点就好了。（因为在重链上的其他点的g数组不会把所改节点的贡献算入，所以不用改）
对着递推式打出的矩阵长这样：
g_{i,0} & g_{i,0}\\
g_{i,1} & -\infty\\
\end{pmatrix}
这样每次访问时让矩阵
f_{i,0}\\
f_{i,1}
\end{pmatrix}$被所有的乘一遍过去就行
```cpp
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define ll long long
#define IR(u,l,r) l<=tree[u].l&&tree[u].r<=r
struct matrix{
ll a[3][3];
matrix(){memset(a,0,sizeof(a));}
matrix operator*(const matrix &b) const
{
matrix c;
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;
}
}val[MAXN];
struct node{
matrix v;
int l,r;
}tree[MAXN<<2];
ll g[MAXN][2],f[MAXN][2];
int dfn[MAXN],cnt,ds[MAXN],n,m;
int sz[MAXN],w[MAXN],top[MAXN],fa[MAXN];
int ed[MAXN],dep[MAXN],tot,head[MAXN];
int wth[MAXN],edge[MAXN*2],Next[MAXN*2];
void upd2(int u)
{
val[u].a[0][0]=val[u].a[0][1]=g[u][0];
val[u].a[1][0]=g[u][1],val[u].a[1][1]=-1e9;
}
void add(int x,int y)
{
edge[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
}
void dfs1(int u)
{
sz[u]=1;
dep[u]=dep[fa[u]]+1;
for(int i=head[u];i;i=Next[i])
{
int v=edge[i];
if(v==fa[u])
continue;
fa[v]=u;
dfs1(v);
sz[u]+=sz[v];
if(sz[v]>sz[w[u]])
w[u]=v;
}
}
void dfs2(int u,int now)
{
top[u]=now;
dfn[u]=++cnt;
ds[cnt]=u;
if(w[u])dfs2(w[u],now),ed[u]=ed[w[u]];
else ed[u]=u;
for(int i=head[u];i;i=Next[i])
{
int v=edge[i];
if(v==fa[u]||v==w[u])
continue;
dfs2(v,v);
}
}
void dfs3(int u)
{
g[u][0]=0,g[u][1]=wth[u];
for(int i=head[u];i;i=Next[i])
{
int v=edge[i];
if(v==fa[u])continue;
dfs3(v);
if(v!=w[u]){
g[u][0]+=max(f[v][0],f[v][1]);
g[u][1]+=f[v][0];
}
}
f[u][0]=g[u][0]+max(f[w[u]][0],f[w[u]][1]);
f[u][1]=g[u][1]+f[w[u]][0];
upd2(u);
}
void pushup(int u)
{
tree[u].v=tree[u*2].v*tree[u*2+1].v;
}
void build(int u,int l,int r)
{
tree[u].l=l,tree[u].r=r;
if(l==r){
tree[u].v=val[l];
return;
}
int mid=(l+r)/2;
build(u*2,l,mid);
build(u*2+1,mid+1,r);
pushup(u);
}
void update(int u,int x)
{
if(tree[u].l==tree[u].r)
tree[u].v=val[x];
else{
int mid=(tree[u].l+tree[u].r)/2;
if(x<=mid)update(u*2,x);
else update(u*2+1,x);
pushup(u);
}
}
matrix query(int u,int l,int r)
{
if(IR(u,l,r))
return tree[u].v;
else{
int mid=(tree[u].l+tree[u].r)/2;
if(r<=mid)return query(u*2,l,r);
if(l>mid)return query(u*2+1,l,r);
return query(u*2,l,r)*query(u*2+1,l,r);
}
}
void updtree(int x,int y)
{
g[x][1]+=y-wth[x];
val[x].a[1][0]=g[x][1];
wth[x]=y;
while(x){
int u=top[x];
matrix now,lst;
lst=query(1,dfn[u],dfn[ed[u]]);
update(1,dfn[x]);
now=query(1,dfn[u],dfn[ed[u]]);
int v=fa[u],vl=max(now.a[0][0],now.a[1][0])-max(lst.a[0][0],lst.a[1][0]);
g[v][0]+=vl;
g[v][1]+=now.a[0][0]-lst.a[0][0];
upd2(v);
x=v;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&wth[i]);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
dfs1(1);
dfs2(1,1);
dfs3(1);
build(1,1,n);
while(m--){
int x,y;
scanf("%d%d",&x,&y);
updtree(x,y);
matrix ans=query(1,dfn[1],dfn[ed[1]]);
printf("%lld\n",max(ans.a[0][0],ans.a[1][0]));
}
return 0;
}
```
代码没调出来，求