你好！我是你的 OI 教练。

这是一道**树形背包（Tree Knapsack）**的必做题。相比于普通的背包问题，它的难点在于“物品之间有依赖关系”，以及如何处理“森林”结构。

下面是符合 NOIP C++14 标准的 AC 代码。我在最关键的状态转移方程和虚拟根节点处理上都加上了详细注释。

标准题解代码 (C++14)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 数据规模：N, M <= 300
// 时间复杂度：O(N * M^2)。300^3 ≈ 2.7 * 10^7，在 1秒限时内是安全的。
const int MAXN = 305;

// dp[u][j]: 以 u 为根的子树中，选择 j 门课程（包含 u 自己）能获得的最大学分
int dp[MAXN][MAXN];

// s[i]: 第 i 门课的学分
int s[MAXN];

// 邻接表存图
vector<int> adj[MAXN];

int n, m;

// 树形 DP / 树上背包核心函数
void dfs(int u) {
    // ================= 初始化 =================
    // 选 u 这个子树，至少得选 u 自己这 1 个点
    // 所以 dp[u][1] 的初始价值就是 u 本身的学分
    dp[u][1] = s[u];

    // ================= 遍历子节点（物品组） =================
    for (int v : adj[u]) {
        dfs(v); // 递归，先计算好子节点 v 的 dp 状态

        // ================= 分组背包转移 =================
        // j: 当前给 u 子树分配的总名额（背包容量）
        // 倒序枚举：防止同一个子树 v 被多次重复利用（和 0/1 背包同理）
        // 范围：从 m+1 到 1。
        // 注意：这里是 m+1，因为我们加了虚拟根节点 0，总共要选 m+1 个点
        for (int j = m + 1; j >= 1; j--) {
            
            // k: 分给子节点 v 的名额
            // 范围：0 到 j-1
            // 为什么是 j-1？因为 u 自己必须占 1 个坑位，
            // 所以分给子树 v 的最大名额不能超过 j-1
            for (int k = 0; k < j; k++) {
                // 状态转移方程：
                // dp[u][j] = max(不选 v 子树的部分, 选 v 子树 k 个 + u 剩余部分 j-k 个)
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
            }
        }
    }
}

int main() {
    // 竞赛标准 IO 优化
    ios::sync_with_stdio(false);
    cin.tie(0);

    if (!(cin >> n >> m)) return 0;

    // 读入数据并建图
    for (int i = 1; i <= n; i++) {
        int k; // 先修课编号
        cin >> k >> s[i];
        
        // k 是 i 的先修课，意味着树中边方向是 k -> i (k 是父亲，i 是儿子)
        // 如果 k=0，表示没有先修课，刚好挂在虚拟根节点 0 下面
        adj[k].push_back(i);
    }

    // 虚拟根节点 0 的学分设为 0
    s[0] = 0;

    // 从虚拟根节点 0 开始 DFS
    // 这样就把“森林”变成了“一棵树”
    dfs(0);

    // 输出答案
    // 题目要求选 M 门课。
    // 但因为我们强制选了 0 号根节点（它不算课，只是连接用的），
    // 所以我们在树上实际选出的节点个数应该是 M + 1
    cout << dp[0][m + 1] << endl;

    return 0;
}

👨‍🏫 教练划重点（易错点解析）

1. 虚拟根节点的必要性：

   • 题目中说“至少一门课无先修课”，这意味着可能有多门课都没有先修课（多棵树，即森林）。
   • 如果不加虚拟根，你需要对每一个无先修课的树根分别跑 DP 再合并，非常麻烦。
   • 技巧：引入 0 号节点，把所有无先修课的节点都连到 0 上。0 号节点的学分为 0。

2. $M$ 变 $M+1$：

   • 因为我们为了连通性，强制选中了虚拟根 0。
   • 所以原本要选 $M$ 门真正的课，变成了在树上选 $M+1$ 个节点。
   • 输出时要输出 dp[0][m+1]。

3. 循环边界与方向：

   • 外层循环 j（背包容量）必须是倒序的。这是背包问题的基本常识，防止同一组物品（子树）在同一个容量层级被叠加多次。
   • 内层循环 k（分配给子树的体积）范围是 0 到 j-1。这里容易写错成 j。必须留 1 的空间给父节点 $u$ 自己，否则 $u$ 都不存在了，怎么挂子树 $v$ 呢？

4. 初始化 dp[u][1] = s[u]：

   • 很多同学会忘记这步，或者写成 dp[u][0] = s[u]。
   • 请记住状态定义：dp[u][j] 是选 $j$ 个点。选 1 个点当然就是只选 $u$ 自己，价值就是 $s[u]$。

这道题是树形背包的基石，请务必完全理解代码中三层循环的含义！加油！

你好！我是你的OI教练。欢迎来到树形DP的经典之作——P2014 选课。

这道题在树形背包问题中的地位，就如同“0/1背包”在背包问题中的地位一样。它是有依赖的背包问题（Dependent Knapsack Problem）的标准模板。弄懂这一题，以后遇到“选这个必须先选那个”的树上问题，你都能迎刃而解。

我们不要急着写代码，先拿出草稿纸，跟我一起构建这个模型。

---

第一部分：思路提示

1. 森林变大树（虚拟根节点技巧）

• 题目说有些课没有先修课（$k_i=0$），这意味着它们是多棵树的根，构成了“森林”。
• 为了方便处理，我们可以创造一个虚拟的 0 号课程（学分是 0），把它作为所有无先修课课程的“先修课”。
• 这样，整个森林就变成了一棵以 0 为根的大树。
• 注意：题目要求选 $M$ 门课，既然我们强制选了 0 号课（作为根），那我们实际要选的课程总数就变成了 $M+1$。

2. 依赖关系的本质

• 要想修课程 $v$，必须先修 $u$。
• 在树上，这意味着：要想选子节点，必须先选父节点。
• 反过来说，如果你选了以 $u$ 为根的子树中的 $k$ 个点，那么 $u$ 本身必须在其中。

3. 树上背包的模型

• 想象一下，节点 $u$ 是一个组长。他有很多个部下（子节点 $v_1, v_2, \dots$）。
• 现在给了 $u$ 一个容量 $j$（我们要在这个子树里选 $j$ 门课）。
• $u$ 首先要把自己选上（消耗 1 个容量，获得 $s_u$ 学分）。
• 剩下的 $j-1$ 个容量，要在 $u$ 的各个子节点（子树）之间分配。
  • 给 $v_1$ 子树分多少？给 $v_2$ 子树分多少？
  • 这不就是分组背包吗？
  • 每一个子节点 $v$ 就是一组物品，这组物品里有“选1个”、“选2个”……“选 $k$ 个”等多种策略。

---

第二部分：预备知识点总结

1. 建图：将“$k_i$ 是 $s_i$ 的先修课”转化为有向边 $k_i \to s_i$。使用邻接表（vector）存储。
2. 虚拟节点：处理 $k_i=0$ 的情况，连接到节点 0。
3. 树形 DP（树上背包）：
   • 状态定义：$dp[u][j]$ 表示在以 $u$ 为根的子树中，选 $j$ 门课能获得的最大学分。
   • 复杂度：虽然看起来像三层循环，但实际复杂度约为 $O(N \cdot M^2)$（对于本题 $300^3 \approx 2.7 \times 10^7$，可以通过）。
4. 分组背包的循环顺序：
   • 外层枚举容量（倒序）。
   • 内层枚举给当前组（子树）分配的体积。

---

第三部分：启发式教学 —— 草稿纸上的推演

来，画图模拟一下。假设有这样一个简单的依赖关系：

0 (虚拟根) -> 1 (学分2) -> 2 (学分3)
             |
             -> 3 (学分4)

我们要选 $M=2$ 门课（实际在树上选 3 个点，含根0）。

第一步：定义 DP 表 $dp[u][j]$：以 $u$ 为根选 $j$ 个点的最大分值。 初始化：所有 $dp$ 值设为 0。

第二步：DFS 后序遍历（自底向上）

1. 处理叶子节点 2

   • 选 1 个（只能选自己）：$dp[2][1] = 3$。
   • 选 0 个：$dp[2][0] = 0$。

2. 处理叶子节点 3

   • 选 1 个（只能选自己）：$dp[3][1] = 4$。
   • 选 0 个：$dp[3][0] = 0$。

3. 处理节点 1（子节点是 2 和 3）

   • 初始状态：选 1 个（选自己）：$dp[1][1] = 2$。
   • 决策时刻 1（考虑子节点 2）：
     • 当前最大容量 $j$ 可以到 3（假设）。
     • 如果我们给节点 1 的子树分配 $j=2$ 个名额：
       • 方案 A：不带 2 玩。$dp[1][2]$ 还没更新，是 0。
       • 方案 B：给 2 分 1 个名额。$dp[1][2-1] + dp[2][1] = 2 + 3 = 5$。
       • 更新 $dp[1][2] = 5$。
   • 决策时刻 2（考虑子节点 3）：
     • 现在 $dp[1]$ 已经是合并了节点 2 之后的结果了。
     • 如果我们给节点 1 的子树分配 $j=3$ 个名额：
       • 给 3 分 1 个名额（剩下 2 个名额给 1 和 2 用）：$dp[1][2] + dp[3][1] = 5 + 4 = 9$。
       • 更新 $dp[1][3] = 9$。

第三步：推导转移方程

对于节点 $u$ 和它的一个子节点 $v$： 我们想计算 $dp[u][j]$（给 $u$ 子树总共 $j$ 个体积）。 我们要枚举分给子树 $v$ 的体积 $k$ ($0 \le k < j$)。

$$dp[u][j] = \max(dp[u][j], \quad dp[u][j-k] + dp[v][k]) $$

• 注意循环顺序：
  1. 遍历子节点 $v$。
  2. 倒序遍历当前容量 $j$（从 $M+1$ 到 1）。
     • 为什么要倒序？和 0/1 背包一样，防止同一个子树 $v$ 在同一个容量 $j$ 里被重复累加。
  3. 遍历分给子树 $v$ 的容量 $k$（从 0 到 $j-1$）。
     • 为什么 $k < j$？因为必须至少留 1 个位置给 $u$ 自己！

代码逻辑框架（填空）：

vector<int> adj[N];
int score[N];
int dp[N][M+2]; // 多开一点防越界
int n, m;

void dfs(int u) {
    // 1. 初始化：选 u 自己，体积为 1，价值为 score[u]
    dp[u][1] = score[u];
    
    // 2. 遍历子节点（物品组）
    for (int v : adj[u]) {
        dfs(v); // 递归算好子节点
        
        // 3. 树上背包转移
        // j 倒序枚举：从 m+1 到 1
        for (int j = m + 1; j >= 1; j--) {
            // k 枚举分给子树 v 的体积
            // k 不能超过 j-1 (因为u自己要占1个)
            // k 甚至可以为 0 (不选v这棵子树)
            for (int k = 0; k < j; k++) {
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
            }
        }
    }
}

int main() {
    // 1. 读入 n, m
    // 2. 读入关系，建立邻接表。注意 k=0 时连接 0 -> i
    // 3. score[0] = 0;
    // 4. dfs(0);
    // 5. 输出 dp[0][m+1] (因为多选了个0号虚拟点)
}

现在，试着把这个逻辑转换成代码吧！别忘了边界 $M$ 要变成 $M+1$ 哦。