浅谈动态DP

· · 算法·理论

1. 引入

Luogu P4719【模板】"动态 DP"&动态树分治：给定一棵 n 个点的树，q 次询问，每次询问修改一个点的权值，请求出每次询问后树上最大权独立集的大小。1\le n,q\le 10^5。

相信大家都会求树上的最大权独立集（没有上司的舞会）：设 f(i,0/1) 表示对于结点 i 的子树，i 不选/选的最大权值，则有

\begin{cases} f(i,0)=\sum_{j\in \text{son}(i)}\max(f(j,0),f(j,1))\\ f(i,1)=val_i+\sum_{j\in \text{son}(i)} f(j,0) \end{cases}

如果直接套上去，时间复杂度 O(nq)，显然会超时。我们需要用一些东西来维护它。

这个东西就是树链剖分。

2. 树链剖分与矩阵乘法

利用树剖找出重结点与轻结点后，不妨尝试分离它们的贡献：设 g(i,0/1) 表示对于结点 i 的子树，仅考虑轻儿子和它本身 时 i 不选/选的最大权值，则有

\begin{cases} g(i,0)=\sum_{j\in \text{lightson}(i)}\max(f(j,0),f(j,1))\\ g(i,1)=val_i+\sum_{j\in \text{lightson}(i)} f(j,0) \end{cases} $$ \begin{cases} f(i,0)=g(i,0)+\max(f(\text{son}(i),0),f(\text{son}(i),1))\\ f(i,1)=g(i,1)+f(\text{son}(i),0) \end{cases} $$ 我们定义一种奇怪的矩阵乘法：~~（虽然我也不知道为什么要这样做）~~ $$ C_{i,j}=\max_{k}(A_{i,k}+B_{k,j}) $$ 其实就是将原来的矩乘中乘法换成加法，加法换成取最大值。它依然满足结合律。 状态转移方程就可以用这种矩阵乘法来表示了： $$ \begin{bmatrix} g(i,0) & g(i,0)\\ g(i,1) & -\infty \end{bmatrix} \times \begin{bmatrix} f(\text{son}(i),0)\\ f(\text{son}(i),1) \end{bmatrix} = \begin{bmatrix} f(i,0)\\ f(i,1) \end{bmatrix} $$ ## 3. 先从序列问题开始！ 跳过之前的题目，我们来看看下面这道题： > [SP1716 GSS3 - Can you answer these queries III](https://www.luogu.com.cn/problem/SP1716)：给定 $n$ 个数字组成的数列 $a$，有 $q$ 次操作，每次操作需要单点修改或者区间查询最大子段和。$1\le n,q\le 5\times 10^4$。 设 $f_i$ 为以 $i$ 结尾的最大子段和，$g_i$ 为从开始到 $i$ 的最大子段和，则有 $$ \begin{cases} f_i=\max(f_{i-1},0)+a_i \\ g_i=\max(f_i,g_{i-1}) \end{cases} $$ 把它转化成矩阵形式： $$ \begin{bmatrix} a_i & -\infty & a_i\\ a_i & 0 & a_i \\ -\infty & -\infty & 0 \end{bmatrix} \times \begin{bmatrix} f_{i-1}\\ g_{i-1}\\ 0 \end{bmatrix} = \begin{bmatrix} f_i\\ g_i\\ 0 \end{bmatrix} $$ 设 $G_i$ 为左边那个矩阵，那么就有 $ans_{l,r}=G_r\times G_{r-1}\times \cdots \times G_l$ 中的第 $(1,0)$ 和第 $(1,2)$ 位最大值。 这玩意...好像可以用线段树来维护？！ - 单点修改 $\to$ 修改对应的 $G$ 矩阵 - 区间查询 $\to$ 统计对应的矩阵连乘积 Perfect！ ## 4. 线段树还可以维护这玩意？！ 我们再回到之前的题目中： 显然一条重链的底端必然是叶子结点。设 $i$ 所在重链底端为 $\text{low}(i)$，那么 $$ \begin{aligned} \begin{bmatrix} f(i,0)\\ f(i,1) \end{bmatrix} &= \begin{bmatrix} g(i,0) & g(i,0)\\ g(i,1) & -\infty \end{bmatrix} \times \begin{bmatrix} f(\text{son}(i),0)\\ f(\text{son}(i),1) \end{bmatrix} \\ &= \begin{bmatrix} g(i,0) & g(i,0)\\ g(i,1) & -\infty \end{bmatrix} \times \begin{bmatrix} g(\text{son}(i),0) & g(\text{son}(i),0)\\ g(\text{son}(i),1) & -\infty \end{bmatrix} \times \begin{bmatrix} f(\text{son}_2(i),0)\\ f(\text{son}_2(i),1) \end{bmatrix} \\ &= \begin{bmatrix} g(i,0) & g(i,0)\\ g(i,1) & -\infty \end{bmatrix} \times \cdots\times \begin{bmatrix} g(\text{low}(i),0) & g(\text{low}(i),0)\\ g(\text{low}(i),1) & -\infty \end{bmatrix} \times \begin{bmatrix} f(\text{son}(\text{low}(i)),0)\\ f(\text{son}(\text{low}(i)),1) \end{bmatrix} \\ &= \begin{bmatrix} g(i,0) & g(i,0)\\ g(i,1) & -\infty \end{bmatrix} \times \cdots\times \begin{bmatrix} g(\text{low}(i),0) & g(\text{low}(i),0)\\ g(\text{low}(i),1) & -\infty \end{bmatrix} \times \begin{bmatrix} 0\\ 0 \end{bmatrix} \end{aligned} $$ 设 $G_i=\begin{bmatrix}g(i,0)&g(i,0)\\g(i,1)&-\infty\end{bmatrix}$，上式可以简化成 $$ \begin{bmatrix} f(i,0)\\ f(i,1) \end{bmatrix} = G_i\times G_{\text{son}(i)}\times G_{\text{son}_2(i)}\times \cdots \times G_{\text{low}(i)}\times \begin{bmatrix} 0\\ 0 \end{bmatrix} $$ 可以发现，$G_i,G_{\text{son}(i)},\cdots,G_{\text{low}(i)}$ 均为这一条重链上的矩阵。 也就是说，**可以用线段树去维护它们和它们的连乘积**。 如果我们已经预处理好了所有结点的 $G$ 矩阵，就可以用线段树方便的求出任意结点的 $f$ 值。 ## 5. 如何修改？ 再次将状态 $g$ 的转移方程列出： $$ \begin{cases} g(i,0)=\sum_{j\in \text{lightson}(i)}\max(f(j,0),f(j,1))\\ g(i,1)=val_i+\sum_{j\in \text{lightson}(i)} f(j,0) \end{cases} $$ 可以发现，**若一个结点的 $g$ 值被修改，当且仅当：** 1. **它的某一个轻子节点 $f$ 值被修改** 2. **自身权值 $val_i$ 被修改** 所以，如果修改结点 $i$ 的权值，$g$ 值发生改变的只可能是它自己和它的祖先结点。 更准确的说，是 **它自己和所有祖先链上轻结点的父亲结点**。 ![](https://cdn.luogu.com.cn/upload/image_hosting/22dpc849.png) （ 图源 OI-Wiki ） > 若结点 10 被修改，$g$ 值改变的是 10,2 两个结点。 > > 若结点 15 被修改，$g$ 值改变的是 15,12,1 三个结点。 > > 若结点 6 被修改，$g$ 值改变的仅有 6 号结点自己。 这跟树链剖分中的跳重链十分相似。所以，可以写出下列代码： ```cpp inline Matrix Find(int x) // 查询结点x的f值 { int y=low[x]; Matrix res; res.r=2,res.c=1,res(0,0)=res(1,0)=0; res=Count(1,n,dfn[x],dfn[y],1)*res; // 自己到链底矩阵的连乘积 return res; } inline void Modify(int x,int y) // 将结点x的权值修改为y { Matrix pre,nxt; g[x](1,0)+=y-val[x]; // 先修改自己,注意这里不要修改线段树上的原矩阵 val[x]=y; while(1) { pre=Find(top[x]); // 修改前的矩阵 Update(1,n,1,dfn[x]); // 更新矩阵 nxt=Find(top[x]); // 修改后的矩阵 x=fa[top[x]]; // 此时x是链上某个轻结点的父亲 if(x==0) break; g[x](0,0)=g[x](0,1)+=max(nxt(0,0),nxt(1,0))-max(pre(0,0),pre(1,0)); g[x](1,0)+=nxt(0,0)-pre(0,0); // 更新该结点的g矩阵 } } ``` ## 6. LCT？全局平衡二叉树！ > [Luogu P4751【模板】"动态DP"&动态树分治（加强版）](https://www.luogu.com.cn/problem/P4751)：给定一棵 $n$ 个点的树，$q$ 次询问，每次询问修改一个点的权值，请求出每次询问后树上最大权独立集的大小，强制在线。$1\le n\le 10^6,\ 1\le q\le 3\times 10^6$。 树剖是 $O(n\log^2n)$ 的，过不去。那有没有什么数据结构， - 时间复杂度为 $O(n\log n)

答案就是：L！C！T！

常！数！大！

卡！不！过！

但是这里的树是静态的，也就是不需要进行连边和断边操作。

所以能不能一开始就把这棵全局平衡树建好，还有着 LCT 的各种性质，而且轻边和重边就是这棵全局平衡树中的虚边和实边呢？

当然可以！

原树 全局平衡树

如何建树？看代码！

inline int BuildChain(int l,int r) // 对于一条重链,构建平衡树,返回根结点
{
    if(l>r) return 0;
    int sum=0,now=0;
    For(i,l,r) sum+=siz[st[i]]-siz[son[st[i]]]; // 权值之和
    For(i,l,r)
    {
        now+=siz[st[i]]-siz[son[st[i]]]; // now为从开始到当前结点的权值和
        if(now*2>=sum) // now刚好超过一半,说明它是重心(根结点)
        {
            int x=st[i];
            ls(x)=BuildChain(l,i-1),rs(x)=BuildChain(i+1,r); // 递归找左右儿子
            fa[ls(x)]=fa[rs(x)]=x,push_up(x); return x;
        }
    }
    return 0;
}
inline int BuildTree(int x) // 递归建树,返回根结点
{
    for(int i=x;i;i=son[i]) // 遍历重链
        for(auto y:v[i])
        {
            if(y==anc[i] || y==son[i]) continue;
            fa[BuildTree(y)]=i; // 连虚边
        }
    top=0;
    for(int i=x;i;i=son[i]) st[++top]=i;
    return BuildChain(1,top); // 对于这条重链建树
}

时间复杂度分析：

所以全局平衡树的深度为 O(\log n) 级别。

在函数 BuildChain 中，某一结点被遍历的次数相当于它在全局平衡树上的深度，所以建树的总时间复杂度为 O(n\log n)。

7. 继续维护！

先来回顾一下，若一个结点的 g 值被修改，当且仅当：

  1. 它的某一个轻子节点 f 值被修改
  2. 自身权值 val_i 被修改

同时，我们还有：任意结点的 f 矩阵等于从它到重链底端 G 矩阵的连乘积乘上 \begin{bmatrix}0\\0\end{bmatrix}。

跟树链剖分时的做法一样，修改结点权值时，暴力跳父亲，如果遇到轻边就查询一遍 f 矩阵再修改父亲结点的 g 值，遇到重边直接向上跳并且 push_up 即可。

可以发现，单次修改的时间复杂度也为 O(\log n)，查询时间复杂度为 O(1)。

inline void Modify(int x,int y) // 将结点x的权值修改为y
{
    Matrix pre,nxt; int pref[2],nxtf[2];
    num[x](1,0)+=y-val[x],val[x]=y; // 修改结点x的g矩阵,但不能修改LCT上的
    while(x)
    {
        pre=t[x],push_up(x),nxt=t[x]; // 上传
        if(isRoot(x) && fa[x]) // 如果它是当前平衡树的根,而且它有父亲
        {
            pref[0]=pre(0,0),pref[1]=pre(1,0),nxtf[0]=nxt(0,0),nxtf[1]=nxt(1,0);
            num[fa[x]](0,0)=num[fa[x]](0,1)+=max(nxtf[0],nxtf[1])-max(pref[0],pref[1]);
            num[fa[x]](1,0)+=nxtf[0]-pref[0];
            // 更新父亲结点的g矩阵
        }
        x=fa[x];
    }
}

8. 边角料：如何处理子树问题？

P6021 洪水：给定一棵 n 个结点的树，q 次操作，每次操作需要单点修改权值或者查询某一棵子树中使得根结点与所有叶子结点不连通需要删除结点的最小权值。1\le n,q\le 2\times 10^5。

状态转移方程和转移矩阵就不列了

如果是树链剖分维护，查询子树的 DP 值非常简单：找到所在重链的叶子结点，用线段树查询连乘积就行了。

那如果是全局平衡二叉树呢？

就像这样，如果查询的是结点 1，那么结点 1 到所在重链叶子结点的矩阵就是被圈出来的这些。

我们就从 1 号结点不断向上跳，如果当前结点是父亲结点的左儿子，就乘上父亲结点和对应的右子树的矩阵即可。

9. 这也可以动态DP？

CF1286D LCC 给定 n 个粒子，每个粒子有初速度，以一定概率向左或向右移动，请求出两个粒子碰撞的期望时间。1\le n\le 10^5。

最早碰撞的两个粒子一定是相邻的粒子。我们可以枚举这一对粒子是什么，以及它们的方向。当然，如果存在有一对粒子比它们更早碰撞的情况，这种情况就应该被禁止。这样就构成了许多的限制，每一种限制形如 \lim(x,a,b)，表示能不能存在第 x-1 个粒子方向为 a，第 x 个粒子方向为 b 的情况。

设 f_{i,0/1} 表示第 i 个粒子方向向左 / 向右的概率，就有

\begin{cases} f_{i,0}=p_{i,0}\times(f_{i-1,0}\times\lim_{i,0,0}+f_{i-1,1}\times\lim_{i,1,0})\\ f_{i,1}=p_{i,1}\times(f_{i-1,0}\times\lim_{i,0,1}+f_{i-1,1}\times\lim_{i,1,1}) \end{cases}

对于每种情况我们按照碰撞时间排序，这样从上一种情况枚举到这一种情况时只需要更改对应的 \lim 值就行了。

但是修改和查询的次数都是 O(n) 级别的，这可怎么办？

上面的式子可以写成矩阵形式！

\begin{bmatrix} p_{i,0}\times\lim_{i,0,0} & p_{i,0}\times\lim_{i,1,0}\\ p_{i,1}\times\lim_{i,0,1} & p_{i,1}\times\lim_{i,1,1} \end{bmatrix} \times \begin{bmatrix} f_{i-1,0}\\ f_{i-1,1} \end{bmatrix} = \begin{bmatrix} f_{i,0}\\ f_{i,1} \end{bmatrix}

然后就是简单的单点修改和区间查询操作了！

这道题便利用了动态 DP 中的转移矩阵思想，并用线段树来维护它。

10. Practice