第十六章 树与图上的动态规划

• 树上动态规划
  • 例1：P1352 没有上司的舞会
  • 例2：P2015 二叉苹果树
  • 例3：P2014 [CTSC1997] 选课
• 图上动态规划
  • 例4：P1613 跑路
  • 例5：P6772 [NOI2020] 美食家
  • 例6：P4316 绿豆蛙的归宿
  • P2656 采蘑菇

树与图上的动态规划，顾名思义，就是以树或图为模型的动态规划。树上动态规划是最常见的动态规划之一，因为树型本身就带来了子结构（树上的父子关系），大部分情况下，都是通过子结点的 $\text{DP}$ 值推导出父结点的 $\text{DP}$ 值。而图上的动态规划，由于没有很明显的子结构，所以比较受限。有向无环图（$\text{DAG}$）由于点之间有着明显的分层，性质相较于图更加良好。许多图上的问题可能转化后称为树上的或 $\text{DAG}$ 上的问题。剩下的许多问题模型，又可以转化为最短路问题。

树上动态规划

例1：P1352 没有上司的舞会

思考如何用子结点的状态推导出父结点的状态。设 $f_u$ 表示 $u$ 号点所在的子树内最大的权之和，$(u, v)$ 为父子关系，可以写出以下式子：

\[f_u = \sum_{v} f_v\]

但这样无法保证题目限制。所以需要设立更多状态。题目中限制了父子关系，而上述转移是子结点向父结点转移。只需要记录自身的相关信息即可，这样转移的时候，既拥有父结点的信息，也拥有子结点的信息。

设 $f_{u, 0}$ 表示 $u$ 号点没有被选时，$u$ 所在子树内最大的权值和；$f_{u, 1}$ 表示 $u$ 号点被选时，$u$ 所在子树内最大的权值和。

\[\begin{aligned} f_{u, 0} & = \sum_v \max(f_{v, 0}, f_{v, 1}) \\ f_{U, 1} & = \sum_v \max(f_{v, 0}) \end{aligned}\]

void DFS(int u) {
    f[u][0] = 0;
    f[u][1] = h[u];
    for (int e = vertex[u].head; e; e = edge[e].next) {
        int v = edge[e].head;
        DFS(v);
        f[u][0] += std::max(f[v][0], f[v][1]);
        f[u][1] += f[v][0];
    }
    return;
}

树上动态规划一般在树的 $\text{DFS}$ 中来完成。因为 $\text{DFS}$ 能够展现出父结点走向子结点，子结点回溯到父结点的过程。

例2：P2015 二叉苹果树

从根开始考虑，枚举其左子树和右子树分别选了多少条边，因为左右子树互相不干扰，所以是独立的子问题。

所以以子树中选了多少条边为状态：$f_{u, x}$ 表示以 $u$ 为根，恰好选了 $x$ 条边，苹果树最大时多少。

\[\begin{aligned} f_{u, x + 1} = \max(f_{u, x + 1}, f_{l, x}) \\ f_{u, y + 1} = \max(f_{u, y + 1}, f_{r, y}) \\ f_{u, x + y + 2} = \max(f_{u, x + y + 2}, f_{l, x} + f_{r, y}) \end{aligned}\]

void DFS(int u, int from) {
    for (int e = vertex[u].head; e; e = edge[e].next) {
        int v = edge[e].head;
        int w = edge[e].weight;
        if (v == from) continue;
        DFS(v, u);
        vertex[u].son += vertex[v].son + 1;
        for (int i = std::min(q, vertex[u].son); i >= 1; i--) {
            for (int j = 0; j <= std::min(i - 1, vertex[v].son); j++) {
                f[u][i] = std::max(f[u][i], f[u][i - j - 1] + f[v][j] + w);
            }
        }
    }
    return;
}

例3：P2014 [CTSC1997] 选课

$f_{u, w}$ 表示根为 $u$ 的子树中，选择 $w$ 个课程，权值和最大时多少。

在转移到父结点的时候，对于每个子树枚举其选择了多少课程。直接枚举的话复杂度是错误的，简单分析发现这是一个分组背包模型。

在 $u$ 为根的子树中，先假设 $u$ 不选。用 $g_{v, w}$ 来辅助背包的转移，表示当前考虑到子树 $v$，一共选了 $w$ 个课程，权之和最大是多少。在枚举到下一个子树 $v’$ 的时候有转移：

\[g_{v', w + w'} = \max_{0 \le w + w' \le m} \\{ g_{v, w} + f_{v', w'} \\}\]

然后再考虑 $u$ 怎么选的情况。当子树中选了 $0$ 个课程，$u$ 可以选，也可以不选。一旦子树中选了 $\gt 0$ 个，$u$ 就不得不选了。记 $v$ 为最后一个枚举到的子树，有转移：

\[\begin{aligned} f_{u, 0} = g_{v, 0} \\ f_{U, w} = g_{v, w - 1} + s_u (w \gt 0) \end{aligned}\]

void DFS(int u) {
    for (int e = vertex[u].head; e; e = edge[e].next) {
        int v = edge[e].head;
        DFS(v);
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= m; j++) {
                g[v][i + j] = std::max(g[i + j], f[u][i] + f[v][j]);
            }
        }
        for (int i = 1; i <= m; i++) f[u][i] = g[v][i];
    }
    if (u == 0) return;
    for (int i = m; i >= 0; i--) f[u][i] = f[u][i - 1] + s[i];
    return;
}

void DFS(int u) {
    f[u][1] = s[u];
    for (int e = vertex[u].head; e; e = edge[e].next) {
        int v = edge[e].head;
        DFS(v);
        for (int i = std::min(vertex[u].size, m + 1); i >= 0; i--) {
            for (int j = 1; j <= vertex[v].size && i + j <= m; j++) {
                f[u][i + j] = std::max(f[u][i + j], f[u][i] + f[v][j]);
            }
        }
        vertex[u].size += vertex[v].size();
    }
    return;
}

图上动态规划

由于路径的分层不是特别明显，一般以路径长度或者点的顺序，或者题目的特殊条件来构造 $\text{DP}$ 状态。

例4：P1613 跑路

由于空间跑路器的存在，直接求出的最短路径不一定是最优解。因此需要对原图做出一定的改变，再求解最短路。

设最优解路径的长度为 $s$，可以得到最优解消耗的时间是在二进制下 $s$ 中 $1$ 的个数。这也等价于将这条路径拆分成若干长度为 $2^k (k \in \N)$ 的路径，每条路径消耗的时间都是一秒。因此只需要关注两点之间是否存在长度为 $2^k$ 的路径。

从而可以构建一张图，如果原图在 $u$ 到 $v$ 存在一条长度为 $2^k$ 的路径，则在新图中连一条 $u$ 到 $v$ 边权为 $1$ 的边。

设 $f_{i, u, v}$ 表示是否存在从 $u$ 到 $v$ 长度为 $2^i$ 的路径（特别的，$f_{0, u, v}$ 表示原图）。如果存在一个 $w$ 使得 $f_{i - 1, u, w} = 1$ 且 $f_{i - 1, w, v}$，则 $f_{i, u, v} = 1$，否则为 $0$。

\[f_{i, u, v} = \bigvee_{w} (f_{i - 1, u, w} \land f_{i - 1, w, v})\]

得到 $f$ 数组后，只需依照 $f$ 数组重新建图，并在新图上求最短路即可得到最后的答案。

void solve() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (adjacency[i][j]) f[0][i][j] = true;
        }
    }
    for (int p = 1; p <= maxP; p++) {
        for (int w = 1; w <= n; w++) {
            for (int u = 1; u <= n; u++) {
                for (int v = 1; v <= n; v++) {
                    f[p][u][v] |= f[p - 1][u][w] & f[p - 1][w][v];
                }
            }
        }
    }
    for (int p = 1; p <= maxP; p++) {
        for (int u = 1; u <= n; u++) {
            for (int v = 1; v <= n; v++) {
                if (f[i][u][v]) dis[u][v] = std::min(dis[u][v], 1);
            }
        }
    }
    for (int w = 1; w <= n; w++) {
        for (int u = 1; u <= n; u++) {
            for (int v = 1; v <= n; v++) {
                if (w != u && w != v && u != v) dis[u][v] = std::min(dis[u][v], dis[u][w] + dis[w][v]);
            }
        }
    }
    return;
}

例5：P6772 [NOI2020] 美食家

注意到边权很小，如果将边拆成若干个点，那么花费 $w_i$ 天相当于经过 $w_i$ 个点。如果不考虑美食节，那么可以经过的点数为状态：定义 $f_{t, v}$ 表示经过 $t$ 个点，当前在点 $v$ 的最大愉悦值。

\[f_{t + 1, v} = \min_{(u, v) \in E} (f_{t, u} + c_v)\]

在美食节的时候，给对应的 $f_{t_i, x_i}$ 加上 $y_i$ 即可。

有一个问题就是 $T$ 特别的大，直接暴力转移是会超时的。此时可以使用矩阵来加速转移。$(\min, +)$ 的矩阵满足结合律，对于边 $(u, v)$，其对应矩阵 $A$ 上 $a_{v, u} = c_v$。对于初始值是向量 $a$，其中 $a_1 = c_1$，其他的 $a_i$ 则赋上一个足够大的值。这样对 $dp$ 的转移就可以使用 $A^k a$ 来表示。

通过预处理 $A^{2^k}$，可以在 $\mathcal O(n^3 \log V)$ 的时间复杂度例获得任意的 $A^V$，其中 $n$ 是矩阵大小，在这题中为 $\mathcal O(n \times \max w_i)$。这样的技巧叫矩阵快速幂优化动态规划。

但是注意到预处理就需要 $\mathcal O(n^3 \log T)$ 的复杂度，而美食节最多又有 $200$ 次，这样也会超时。原因是矩阵乘法是 $\mathcal O(n^3)$ 的，所以需要采用更快的矩阵乘向量，时间复杂度为 $\mathcal O(n^2)$。

这样就可以用 $\mathcal O(n^2 \log V)$ 时间复杂度，让动态规划转移 $V$ 次。最终时间复杂度为 $\mathcal O(n^2 (n + k) \log T)$。

在有向无环图的动态规划中，由于拓扑序导致拓扑序小的点只依赖拓扑序大的点，将拓扑序作为构造动态规划状态的依据十分合适。有些题目经过转化，也能够将一般图上的问题转化为有向无环图上的问题。

例6：P4316 绿豆蛙的归宿

记 $d_u$ 为 $u$ 的出边数量，$w$ 为边的长度，$f_u$ 为从 $u$ 走到终点时路径的期望长度，那么有转移：

\[f_u = \sum_{(u, v) \in E} \frac{f_v + w_(u, v)}{d_u}\]

拓扑序小的依赖拓扑序大的，因此按拓扑序从大到小转移即可。

void mian() {
    std::queue<int> q;
    q.push(n);
    f[n] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int e = vertex[u].head; e; e = edge[e].next) {
            int v = edge[e].head;
            int w = edge[e].weight;
            f[v] += (f[u] + w) / vertex[v].cnt;
            vertex[v].deg--;
            if (!vertex[v].deg) q.push(v);
        }
    }
    printf("%.2lf", f[1]);
    return;
}

P2656 采蘑菇

如果两条边在同一个强连通分量，那么它们会同时被走完或者同时不被走。所以可以通过强连通分量算法，将图变成一个边有边权 $w$，点有点权 $p$ 的有向无环图。其中路径的权值定义为边权和点权之和。找到 $S$ 所在的强连通分量后，问题倍增转化为在有向无环图上，从一个点出发的最长路径。

对于每个点 $u$ 记 $f_u$ 为从 $u$ 出发的最长路径，可以写出转移：

\[f_u = \max_{(u, v) \in E} (w_{(u, v)} + f_v) + p_u\]

对于每个点，其 $f$ 值只依赖拓扑序比它大的点，所以要按拓扑序从大到小进行动态规划。使用拓扑排序即可完成。