【笔记】动态 DP

【笔记】动态 DP

这个算法的名字好毒瘤的样子。。。Dynamically Dynamical Programming,动态 – 动态规划,简称 DDP。

我们先考虑简单的动态规划。有一个经典问题叫做树上最大权独立集。比如 没有上司的舞会

那么我们可以设 $f_{u,1}$ 为 $u$ 在独立集内的最大收益,$f_{u,0}$ 为 $u$ 不在独立集内的最大收益。转移方程如下:

$$f_{u,1}=\sum_{v\in son}f_{v,0}$$
$$f_{u,1}=\sum_{v\in son}\max (f_{v,0},f_{v,1})$$

现在我们要支持的操作是动态修改某个点的权值,比如 洛谷模板

为了快速维护,我们先对整棵树做一个树剖,然后对每一条重链分别进行 dp。

对于重链上的每个点,先根据轻儿子的 $f$ 维护 $g_{u,1/0}$:

$$g_{u,0}=\sum_{v\in lightson}\max(f_{v,0},f_{v,1})$$

$$g_{u,1}=\sum_{v\in lightson} f_{v,0}$$

对于重链上的点,则有:

$$f_{u,0}=g_{u,0}+\max(f_{heavyson,0},f_{heavyson,1})$$

$$f_{u,1}=g_{u,1}+f_{heavyson,0}$$

这样,树上的问题就转化成了序列上的问题。我们可以对于每条重链维护一颗线段树。修改一个点的值就在这个点所在重链的线段树上修改,最后改变了重链顶端的点的 $f$ 值,进而影响了其父亲的 $g$ 值,反复向上修改,时间复杂度就是 $\Theta(log^2n)$ 的。

问题来了,如何用线段树维护 $f$ 呢。我们重新定义矩阵乘法。对于 $C=A\times B$,有

$$C_{i,j}=\max\limits_{k=1}^{n}(A_{i,k}+B_{k,j})$$

于是,重链上的转移可以写成这样的矩乘

$${\left[ \begin{array}{cc}g_{i,0} &g_{i,0}\\ g_{i,1} &0\end{array} \right ]}\times{\left[ \begin{array}{cc}f_{i+1,0} & f_{i,0}\\ f_{i+1,1} & 0 \end{array} \right ]}={\left[ \begin{array}{cc}f_{i,0}\\ f_{i,1} \end{array} \right ]}$$

重定义以后的矩阵乘法依然满足结合律。我们在线段树上维护矩阵的连乘积,可以实现 $\Theta(8log^2n)$ 的修改操作。

总结一下思路:树剖,维护区间矩阵乘积。修改时从被修改节点所在重链不断向上跳。每次答案就是 $root$ 的 $f$ 值。

伪代码

#include 
#define ll long long
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
#define maxn 1000100
using namespace std;
struct Edge{
    int to,next;
    Edge(int a=0,int b=0){
        to=a,next=b;
    }
}l[maxn<<1];
struct Matrix{
    ll g[2][2];
    Matrix operator * (const Matrix &x) const{
        Matrix r;
        for (register int i=0;i<2;++i)
            for (register int j=0;j<2;++j)
                for (register int k=0;k<2;++k)
                    r.g[i][j]=max(r.g[i][j],g[i][k]+x.g[k][j]);
        return r;
    }
}val[maxn],tree[maxn];
int head[maxn],vl[maxn],wid[maxn];
int cnt,n,m;
int top[maxn],id[maxn],fa[maxn];
int siz[maxn],son[maxn],nv[maxn],ed[maxn];
ll f[maxn][2];
void Add(int a,int b){
    l[++cnt]=Edge(b,head[a]);
    head[a]=cnt;
}
void Pre_Work(int u,int f){
    fa[u]=f,siz[u]=1;
    int maxson=-1;
    for (register int i=head[u];i;i=l[i].next){
        int v=l[i].to;
        if (v==f) continue;
        Pre_Work(v,u);
        siz[u]+=siz[v];
        if (siz[v]>maxson)
            maxson=siz[v],son[u]=v;
    }
}
void Re_Build(int u,int topf){
    top[u]=topf;wid[id[u]=++cnt]=u;
    nv[cnt]=vl[u];
    if (!son[u]) {ed[topf]=cnt;return;}
    Re_Build(son[u],topf);
    for (register int i=head[u];i;i=l[i].next){
        int v=l[i].to;
        if (v==fa[u]||v==son[u]) continue;
        Re_Build(v,v);
    }
}
void Get_f(int u){
    f[u][1]=max(0,vl[u]);
    for (register int i=head[u];i;i=l[i].next){
        int v=l[i].to;
        if (v==fa[u]) continue;
        Get_f(v);
        f[u][1]+=f[v][0];
        f[u][0]+=max(f[v][0],f[v][1]);
    }
}
void Build(int l,int r,int p){
    if (l==r){
        ll g0=0,g1=a[wid[l]];
        for (register int u=wid[l],i=head[u];i;i=l[i].next){
            int v=l[i].to;
            if (v==fa[u]||v==son[u]) continue;
            g0+=max(f[v][0],f[v][1]);
            g1+=f[v][0];
        }
        tree[p].g[0][0]=tree[p].g[0][1]=g0;
        tree[p].g[1][0]=g1;
        return;
    }
    Build(l,mid,ls),Build(mid+1,r,rs);
    tree[p]=tree[ls]*tree[rs];
}
void Update(int l,int r,int t,int p){
    if (l==r){tree[p]=val[l];return;}
    if (t<=mid) Update(l,mid,t,ls);
    else Update(r,mid+1,t,rs);
    tree[p]=tree[ls]*tree[rs];
}
Matrix Query(int l,int r,int L,int R,int p){
    if (l>=L&&r<=R) return tree[p];
    if (R<=mid) return Query(l,mid,L,R,ls);
    if (L>mid) return Query(mid+1,r,L,R,rs);
    return Query(l,mid,L,R,ls)*Query(mid+1,r,L,R,rs);
}
Matrix Ask(int u){
    return Query(1,n,id[top[u]],ed[top[u]],1);
}
void Path_Change(int u,int x){
    val[id[u]].g[1][0]+=x-vl[u];
    vl[u]=x;
    Matrix lst,cur;
    while(u){
        lst=Ask(top[u]);
        Update(1,n,id[u],1);
        cur=Ask(top[u]);
        u=fa[top[u]];
        val[id[u]].g[0][0]+=max(cur.g[0][0],cur.g[1][0])-max(lst.g[0][0],lst.g[1][0]);
        val[id[u]].g[0][0]=val[id[u]].g[0][0];
        val[id[u]].g[1][0]+=cur.g[0][0]-lst.g[0][0];
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for (register int i=1;i<=n;++i)
        scanf("%d",vl+i);
    for (register int i=1,a,b;i