形式化题目

给定 $N$ 门课程，每门课 $i$ 有一个直接先修课 $p_i$（$p_i = 0$ 表示无先修课）和一个正整数学分 $w_i$。 选出一个恰好 $M$ 门课的集合 $S$，满足先修闭包条件

最大化总学分 $\sum_{i \in S} w_i$。

「每门课的直接先修课最多只有一门」意味着每个点最多有一条指向父亲的边，因此先修关系无环， 构成一片森林（森林中的有根树以 $p_i = 0$ 的课为根）。题目没有限制一门课可以被几门课后修， 所以树可以是任意形状。

将森林中所有根都挂到一个虚拟点 $0$（$w_0 = 0$）下，森林变成一棵以 $0$ 为根的树 $T$， 问题等价于：在 $T$ 中选恰好 $M + 1$ 个点、必须包含 $0$、且若选 $v$ 则选其父亲，最大化点权和。

题面样例：$N = 7$，$M = 4$，各课的先修课与学分为 $p = [\_,\,2,\,0,\,0,\,2,\,7,\,7,\,2]$、$w = [\_,\,2,\,1,\,4,\,1,\,1,\,6,\,2]$ （下标 0 是占位，下标 $i$ 对应课号 $i$）。

按先修关系建树（括号内为学分）：

1
2
3
4
5
6
7
80(0)
├── 2(1)
│   ├── 1(2)
│   ├── 4(1)
│   └── 7(2)
│       ├── 5(1)
│       └── 6(6)
└── 3(4)

最优解是 $S = \{2, 3, 6, 7\}$：2、3 先修课为 0 可以直接选；7 的先修课 2 已在 $S$ 中； 6 的先修课 7 也在 $S$ 中。学分 $1 + 4 + 6 + 2 = 13$。

正解

思路

先问枚举能不能做。 候选方案是全部 $\binom{7}{4}$（一般地 $\binom{N}{M}$）个课程子集， 逐个检查先修闭包花 $O(N)$。$N = 300$ 时 $\binom{300}{150} \approx 10^{89}$，枚举不可行。

直接背包为什么也不对。 一个自然的想法是「设 $f[j]$ 为选 $j$ 门课的最大学分」， 逐个课程做 0/1 背包。但这个状态没有记录先修课有没有被选：样例中课程 6 的学分是 6、 先修课是 7，只记门数的背包会在 7 还没被选上的情况下就给 6 记账，得到虚高的答案。 这就是「有依赖的背包」必须比普通背包多带一层结构的原因——决策变量之间存在 树形偏序，而纯粹的容量维度表达不了它。

关键观察：约束只沿父子边，所以子树可以独立压缩。 固定节点 $v$ 之后：

• $v$ 的各个儿子子树之间没有任何边（树里没有横叉边），彼此独立；
• $v$ 的子树与外界（$v$ 的祖先）唯一的联系就是 $v$ 自己。

所以对 $v$ 的父亲而言，它不关心 $v$ 子树内部到底选了哪些点，只关心 「在这棵子树里花掉 $j$ 个名额，最多能拿多少学分」。这正好可以把子树压成一张关于 $j$ 的表：

转移。 初值 $dp[v][1] = w_v$，其余为 $-\infty$（名额连 $v$ 自己都装不下就没有合法方案）。 然后依次把每个儿子 $u$ 的子树合并进来，枚举分给 $u$ 的名额 $k$ 与已合并部分的现有名额 $j$：

对照 3148「没有上司的舞会」可以看得更清楚：那道题没有名额限制，父亲对儿子只需要一个布尔约束 （来 / 不来），所以每个点压成两档就够；本题有全局名额预算 $M$， 父亲必须把预算在儿子之间切分，所以状态必须带一维「用掉多少名额」， 合并动作也就从「取 $\max$」变成「分组背包」。

计算顺序。 $dp[v]$ 依赖儿子，所以必须后序遍历（子在父前）。 本题 $N \leqslant 300$，递归深度不大，但代码仍用显式栈求后序，不依赖解释器的递归上限。

两个容易写错的细节。

1. $j$ 必须倒序枚举。 best 在这一轮里既是「合并前的旧表」又是「合并中的新表」， 正序会让同一个儿子被重复使用（同一子树的收益被计两次）。这与一维 01 背包滚动数组的方向完全同源。
2. $k$ 从 1 开始。 $dp[u][0]$ 是非法档（选了 $u$ 才谈得上选它子树里的点）， 而「完全不要 $u$ 的子树」根本不需要在 $k$ 循环里表达——它对应「本轮不更新 $best$」， 原值自然保留。

样例推演。 后序处理顺序是 $1, 4, 5, 6, 7, 2, 3, 0$。每个叶子只有 $dp[v][1] = w_v$ 一档有值， 下表给出每个节点合并完全部儿子后的完整 $dp$ 表（预算 $M + 1 = 5$，-∞ 表示该档不可达）：

四个叶子（1、4、5、6）只有第 1 列有值，印证了 $dp[\text{leaf}][1] = w_{\text{leaf}}$ 的初值。 节点 2 那一行是本题的缩影：$dp[2][1] = 1$（只能是 2 自己）、$dp[2][2] = 3$（2 加上学分最大的儿子 1）、 $dp[2][3] = 9$（子集 $\{2, 7, 6\}$，学分 $1 + 2 + 6$）、 $dp[2][5] = 12$——注意 2 的子树共 6 个点，名额只有 5 个，且选的集合必须封闭， 所以只能丢掉一个叶子；背包丢掉学分最小的叶子（1 分的 4 或 5）， 例如选 $\{2, 1, 7, 5, 6\}$ 得 $1 + 2 + 2 + 1 + 6 = 12$。 下面把节点 7（它有两个儿子 5、6）的合并过程逐格展开，看清单个儿子的子树是如何被并入的：

读表要点：单元格的值是「花掉该列名额能拿到的最大点权和」。并入儿子 5 时， $j = 1$ 的旧值 2 与 $k = 1$ 的 $dp[5][1] = 1$ 合成新档 $j = 2$ 的 3； 并入儿子 6 时同理，$2 + 6 = 8$ 落在 $j = 2$（7 与 6）、$3 + 6 = 9$ 落在 $j = 3$（再加一个儿子 5）。 注意 $dp[7][2]$ 拿到的是 6 的 6 分而不是 5 的 1 分——说明名额分配由背包自己挑最优的一支， 不需要预先指定要哪个儿子。 每一步只允许「保留旧值」或「用掉 $k$ 个名额换 $dp[u][k]$」，绝对不会把同一个儿子用两次—— 这就是 $j$ 倒序枚举的效果。

再看根节点 0 的合并：初始只有 $dp[0][1] = 0$（根白占一格）。并入儿子 2 时 用上表 $dp[2]$ 那一行，得到 $(0, 1, 3, 9, 11)$；再并入儿子 3（$dp[3][1] = 4$）， 最终 $(0, 4, 5, 9, \mathbf{13})$。答案 $dp[0][5] = 13 = dp[2][3] + dp[3][1] = 9 + 4$， 即「根 0 白占一格 + 节点 2 的子树里选 3 个点（取到 $\{2, 7, 6\}$）+ 节点 3 自己」。 这正好是样例的最优解 $S = \{2, 3, 6, 7\}$，验证了 $dp[0][M+1]$ 就是答案。

代码

read_courses 一边读入一边把「先修课 → 本课」建成孩子表（虚拟根 0 的孩子们就是所有无先修课的课）； postorder 用显式栈产出「子在父前」的处理顺序；best_credits 里局部变量 best 就是 $dp[v]$， NEG 就是 $-\infty$，内层双重循环就是上面那条分组背包转移式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 选课：先修关系构成森林，虚拟根 0 连成树，树上背包求最高学分。
#include <cstdio>
#include <vector>

typedef long long ll;

const ll NEG = -1000000000LL; // 「这个门数凑不出来」的哨兵

ll n, m;
std::vector<std::vector<int> > children;
std::vector<ll> credits;
std::vector<std::vector<ll> > dp; // dp[v][j]：在 v 的子树里选 j 门课（必含 v）的最高学分
std::vector<ll> subtree;          // 子树节点数，用于裁剪背包循环

int main() {
    if (scanf("%lld %lld", &n, &m) != 2) return 0; // 空输入安全返回
    children.assign(n + 1, std::vector<int>());
    credits.assign(n + 1, 0);
    for (ll course = 1; course <= n; course++) {
        int prereq;
        scanf("%d %lld", &prereq, &credits[course]);
        children[prereq].push_back((int)course); // 先修课就是父亲
    }

    ll budget = m + 1; // 虚拟根 0 也占一门课的预算

    // 后序遍历（显式栈，避免深递归）
    std::vector<int> order;
    std::vector<int> stk;
    stk.push_back(0);
    while (!stk.empty()) {
        int u = stk.back();
        stk.pop_back();
        order.push_back(u);
        for (size_t j = 0; j < children[u].size(); j++) stk.push_back(children[u][j]);
    }

    dp.assign(n + 1, std::vector<ll>());
    subtree.assign(n + 1, 0);
    for (size_t t = order.size(); t-- > 0;) {
        int node = order[t];
        std::vector<ll> best(budget + 1, NEG);
        if (budget >= 1) best[1] = credits[node]; // 先备好「只选 node 自己」
        ll used = 1; // 已合并部分最多能贡献的门数
        for (size_t c = 0; c < children[node].size(); c++) {
            int child = children[node][c];
            ll sub_cap = subtree[child] < budget ? subtree[child] : budget;
            for (ll j = (used < budget ? used : budget); j >= 1; j--) { // j 倒序扫
                if (best[j] == NEG) continue;
                ll kmax = (sub_cap < budget - j) ? sub_cap : (budget - j);
                for (ll k = 1; k <= kmax; k++) {
                    ll cand = best[j] + dp[child][k];
                    if (cand > best[j + k]) best[j + k] = cand;
                }
            }
            used += sub_cap;
            if (used > budget) used = budget;
        }
        subtree[node] = used;
        dp[node] = best;
    }

    printf("%lld\n", dp[0][budget]);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 21:08
# update_at: 2026-10-01 21:20

import sys
from collections.abc import Iterator

NEG = -10**9  # 「这个门数凑不出来」的哨兵；学分都是正整数，不会和真实答案混淆


def read_courses(data: Iterator[int], n: int) -> tuple[list[list[int]], list[int]]:
    """读 N 行「先修课 学分」，返回孩子表与学分表（课程编号 1..N）。

    「每门课的直接先修课最多只有一门」意味着 {先修课 -> 本课} 是一张森林；
    把虚拟根 0 当成所有无先修课的课的父亲，森林就变成以 0 为根的树。
    """
    children: list[list[int]] = [[] for _ in range(n + 1)]
    credits: list[int] = [0] * (n + 1)
    for course in range(1, n + 1):
        prereq = next(data)              # 本课的直接先修课，0 表示没有
        credits[course] = next(data)
        children[prereq].append(course)  # 先修课就是父亲
    return children, credits


def postorder(children: list[list[int]], root: int) -> Iterator[int]:
    """后序遍历整棵树：显式栈先压出「父在子前」的序列，反转就是「子在父前」。"""
    order: list[int] = []
    stack = [root]
    while stack:
        node = stack.pop()
        order.append(node)
        stack += children[node]
    yield from reversed(order)


def best_credits(children: list[list[int]], credits: list[int], m: int) -> int:
    """树上背包：dp[v][j] = 在 v 的子树里选 j 门课（必含 v）能拿到的最高学分。

    先修关系要求「选一门课就得选它的先修课」，于是 v 被选了，儿子们才有资格选；
    反过来，儿子子树之间互不影响，可以用「按门数合并」的背包式子拼起来。
    虚拟根 0 也占一门课的预算，所以总预算取 M+1，答案落在 dp[0][M+1]。
    """
    budget = m + 1
    dp: list[list[int]] = [[] for _ in range(len(children))]
    subtree = [0] * len(children)  # 子树节点数被 min(·, budget) 封顶，用于裁剪背包循环
    for node in postorder(children, 0):
        best = [NEG] * (budget + 1)
        best[1] = credits[node]  # 先备好「只选 node 自己」这一档
        used = 1                 # 已合并部分最多能贡献的门数
        for child in children[node]:
            sub, sub_cap = dp[child], min(subtree[child], budget)
            for j in range(min(used, budget), 0, -1):  # j 倒序扫，避免同一个儿子被选两次
                if best[j] == NEG:
                    continue
                for k in range(1, min(sub_cap, budget - j) + 1):
                    cand = best[j] + sub[k]
                    if cand > best[j + k]:
                        best[j + k] = cand
            used = min(used + sub_cap, budget)
        subtree[node] = used
        dp[node] = best
    return dp[0][budget]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    children, credits = read_courses(data, n)

    print(best_credits(children, credits, m))


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：$O(NM)$。建树与求后序各 $O(N)$；背包合并的瓶颈是「已合并部分名额 $j$」乘 「分给儿子 $u$ 的名额 $k$」。代码用 used 把 $j$ 限制在已合并节点数内、用 sub_cap 把 $k$ 限制在儿子子树大小内，于是每一步相乘对应一对「已并入的点 $\times$ 新并入的点」， 每对点只在它们的最小公共祖先处被计一次，总量为 $O(NJ) = O(NM)$（$J = M+1$）。 实测 $N = 300$ 的链、完全二叉树、星形等最坏结构下内层比较约 $10^4 \sim 4.5 \times 10^4$ 次， 单次运行约 0.02s，远低于 1000ms 限制。
• 空间复杂度：$O(NM)$。每个节点存一张长度 $M + 2$ 的表；$N \leqslant 300$ 时 峰值内存约 15MB，低于 128MB 限制。

总结

本题是树上背包（也叫「有依赖的背包」）的模板题，核心有三步：

1. 把森林变成树：给所有无先修课的课加一个学分为 $0$ 的虚拟根 $0$， 「选 $M$ 门课」就变成「在以 $0$ 为根的树里选 $M + 1$ 个点、含根、且选了点就选其父亲」。
2. 确认子树可独立压缩：约束只沿父子边，子树与外界只有根一个接触点， 所以每个子树可以压成一张「花 $j$ 个名额的最大收益」表 $dp[v][j]$。
3. 子树之间做分组背包：给 $v$ 的预算要分给各个儿子，合并时 $j$ 倒序、$k$ 从 1 开始， 答案取 $dp[0][M+1]$。

值得记住的对照是：没有名额限制的树形 DP（两档状态）和有依赖的背包（带容量维）差别正在预算。 一旦父亲需要把预算在儿子之间切分，「每点两档」就不够用了。

图示解析

这张图串起从题意到答案的主线：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24输入：N 门课，各自有「直接先修课」（最多一个）与学分
  |
  |  枚举 C(N,M) 个子集不可行（N=300）
  v
关键结构：每点最多一条指向父亲的边 -> 先修关系是一片森林
  |
  |  加虚拟根 0（学分 0），把森林变成一棵以 0 为根的树
  v
关键观察：约束只沿父子边
  |- 各儿子子树之间没有边，彼此独立
  `- 子树与外界的唯一联系是 v 自己
        |
        v
  每个 v 压成一张表：dp[v][j] = v 子树里选 j 个点（含 v）的最大点权和
        |
        |  初值 dp[v][1] = w_v
        |  合并儿子 u：dp[v][j+k] = max(dp[v][j+k], dp[v][j] + dp[u][k])
        |             j 倒序防重用；k >= 1（选了 u 才谈得上它子树）
        v
  计算顺序：后序遍历，儿子先于父亲（显式栈，不依赖递归上限）
        |
        |  预算 = M+1（虚拟根占一格）
        v
  答案 dp[0][M+1]                 O(NM) 时间、O(NM) 空间

观察重点：整条链路上真正的转折点只有一处——把「全局选一个子集」拆成「每个子树独立算一张表」。 能做到这一步，靠的是「每门课的直接先修课最多只有一门」这条限制带来的树形结构； 如果允许一门课有多个先修课，关系就变成一般 DAG，「取一个点必须取其全部前驱」不再是树上的父子约束， 本做法不再适用。最后答案之所以落在 $dp[0][M+1]$ 而不是某个真实课程上， 是因为虚拟根只是记账用的，它占掉的那一个名额正好把「$M$ 门课」换算成「$M+1$ 个点」。