绿【树形动态规划、DFS序】选课

题意概括

给定包含 $N$ 个节点与 $M$ 个选取配额的依赖网络。节点 $i$ 具有权值 $s_i$ 与唯一的直接前置依赖节点 $k_i$（若 $k_i=0$ 则无依赖）。依赖关系整体构成森林拓扑。现要求在严格满足拓扑依赖律（即选取节点 $i$ 的必要条件为节点 $k_i$ 已被选取）的前提下，选取恰好 $M$ 个节点，最大化所选节点的权值总和。

数据范围：$1 \leq N, M \leq 300$，$0 \leq k_i \leq N$，$1 \leq s_i \leq 20$。

样例分析

针对给定样例，我们可引入权值为 $0$ 的虚拟根节点 $0$。依赖森林即转化为以 $0$ 为根的有向树。其拓扑结构映射如下：

节点 $0$ 连向子节点 $2, 3$；节点 $2$ 连向子节点 $1, 4, 7$；节点 $7$ 连向子节点 $5, 6$。

目标等价于在包含节点 $0$ 的前提下，自该树中选取 $M+1 = 5$ 个节点。

依据贪心与局部最优结构，最优子树组合为选取节点集合 $\{0, 2, 3, 7, 6\}$。

对应权值总和求值为：

$$0 + 1 + 4 + 2 + 6 = 13$$

此即理论最大收益。

题目分析

常规的树上背包动态规划算法在合并子树状态时，需利用嵌套循环枚举各子树分配的容量，其状态转移的时间开销会导致整体时间复杂度退化至 $\mathcal{O}(N M^2)$。为严密贴合 $\mathcal{O}(NM)$ 的最优渐进下界，我们需要对树形依赖关系进行降维，引入 DFS 序（深度优先搜索遍历序列）将树上问题同构映射为线性序列问题。

定义 $dfn[i]$ 为树的前序遍历序列中第 $i$ 个被访问的节点标号，并设 $sz[u]$ 为以 $u$ 为根的子树的节点基数。

此时建立二维状态矩阵：令 $f[i][j]$ 表示仅考虑 DFS 序的后缀区间 $[i, N+1]$，且选取恰好 $j$ 个节点时所能获取的最大权值。

对于位于 DFS 序第 $i$ 位的节点 $u = dfn[i]$，面临二元决策：

1. 若决策不选取节点 $u$，受限于拓扑约束律，其所有后代节点均不可达。此时序列处理指针必须发生跃迁，直接跨越整棵子树，转移至 $i + sz[u]$ 的位置。
2. 若决策选取节点 $u$，则状态合法化，序列处理指针推进至 DFS 序的紧邻后继 $i + 1$（即其首个子节点），且剩余可选容量衰减 $1$。

由此可提取形式化的状态转移方程：

$$f[i][j] = \max(f[i+sz[u]][j], f[i+1][j-1] + val[u]) $$

初始边界条件设为：$f[N+2][0] = 0$，其余状态初始化为 $-\infty$。我们对 DFS 序列执行自底向上的逆序动态规划推演，最终所求的全局最优解即收敛于 $f[1][M+1]$。该模型状态总数严格为 $\mathcal{O}(NM)$，且每次转移的计算代价为 $\mathcal{O}(1)$，从根本上消除了分配多项式复杂度的可能。

参考实现

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m;
int h[305], nxt[305], to[305], edg;
int val[305], sz[305], dfn[305], id;
int f[305][305];

void add(int u, int v) {
    to[++edg] = v;
    nxt[edg] = h[u];
    h[u] = edg;
}

void dfs(int u) {
    dfn[++id] = u;
    sz[u] = 1;
    for (int i = h[u]; i; i = nxt[i]) {
        int v = to[i];
        dfs(v);
        sz[u] += sz[v];
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int k, s;
        cin >> k >> s;
        add(k, i);
        val[i] = s;
    }
    dfs(0);
    for (int i = 0; i <= id + 1; ++i) {
        for (int j = 0; j <= m + 1; ++j) {
            f[i][j] = -1e9;
        }
    }
    f[id + 1][0] = 0;
    for (int i = id; i >= 1; --i) {
        int u = dfn[i];
        for (int j = 0; j <= m + 1; ++j) {
            f[i][j] = f[i + sz[u]][j];
            if (j > 0) {
                f[i][j] = max(f[i][j], f[i + 1][j - 1] + val[u]);
            }
        }
    }
    cout << f[1][m + 1] << "\n";
    return 0;
}

复杂度分析

时间复杂度：$\mathcal{O}(NM)$。预处理阶段的前序遍历耗时 $\mathcal{O}(N)$，动态规划阶段的状态空间规模为 $(N+1) \times (M+1)$，单个状态转移的计算步数为严格常量级 $\mathcal{O}(1)$，故渐进时间复杂度上界为 $\mathcal{O}(NM)$。

空间复杂度：$\mathcal{O}(NM)$。状态矩阵的阶数为 $N \times M$，图与序列所占用的线性表空间均为 $\mathcal{O}(N)$。整体内存开销受限于状态矩阵，渐进空间复杂度为 $\mathcal{O}(NM)$。

https://www.luogu.com.cn/problem/P2014