你好！我是你的OI金牌教练。

我们继续在历史的长河中探索算法。上一题我们结合“汉武帝推恩令”，学习了 “父子不能同时选” 的树形 DP（最大权独立集）。

今天，我们回到战国时期，结合 “战国四公子”之首——孟尝君 的故事，来学习树形 DP 的另一类经典模型——“有依赖的背包问题”（父子依赖关系：选子必选父）。

这道题在知识点上与上一题形成了鲜明的对照与递进：

1. 对照：上一题是“互斥”（选父不能选子），这一题是“依赖”（选子必须选父）。
2. 递进：上一题的状态只有“选/不选”两种，这一题的状态是“选多少个”，结合了背包 DP 的思想，复杂度从 $O(N)$ 提升到了 $O(N \cdot M)$。

这是 GESP 6级 乃至 7级 的高频难点。

---

第一部分：背景知识讲解

1. 孟尝君养士 (Lord Mengchang's Patronage)

战国时期，齐国的孟尝君（田文）以好客养士闻名天下，号称“食客三千”。 这些门客（食客）各有专长，有“鸡鸣狗盗”之徒，也有冯谖（xuān）这样的治国奇才。

2. 门客的等级与推荐制

在庞大的门客体系中，存在着严格的推荐与依附关系。

• 通常，一位高级门客会推荐自己的亲信或弟子投奔孟尝君。
• 如果要重用（选中）某位低级门客去执行任务，通常需要同时重用他的推荐人（上级），以便于指挥和协调。
• 这就形成了一个树状的依赖结构：要想使用子节点的力量，必须先激活父节点。

3. 算法模型：树上背包 (Tree Knapsack)

假设孟尝君遇到了一件棘手的大事，需要挑选 $M$ 位门客组成“特遣队”。 每位门客都有一个能力值。 限制条件：如果选了某个人，就必须选他的直接上级（推荐人）。（除了孟尝君自己）。 目标：在刚好选 $M$ 个人的前提下，让总能力值最大。

---

第二部分：题目内容

题目名称：孟尝君的门客 (Lord Mengchang's Retainers)

题目描述

战国时期，孟尝君门下食客三千，形成了一个等级森严的树形组织。 共有 $N$ 名门客，编号为 $1$ 到 $N$。其中 $1$ 号是孟尝君本人（根节点）。 除了孟尝君，每位门客都有唯一的直接上级。

为了出使秦国，孟尝君决定从这 $N$ 人中恰好挑选 $K$ 人（必须包含孟尝君自己）组成使团。 每位门客都有一个智谋值 $V_i$。 选人规则如下：如果选择了门客 $u$，则必须同时选择 $u$ 的直接上级。 （这意味着，被选中的 $K$ 个人必须构成一个包含根节点的连通子树）。

请你编写程序，计算在满足规则的前提下，这 $K$ 个人的智谋值之和的最大值。

输入格式

第一行包含两个正整数 $N, K$。

• $N$ 表示门客总数。
• $K$ 表示需要组建的使团人数。

接下来 $N$ 行，每行包含两个整数 $P_i, V_i$。

• 第 $i$ 行的数据描述编号为 $i$ 的门客。
• $P_i$ 表示门客 $i$ 的直接上级编号。如果 $P_i = 0$，表示他是根节点。
• $V_i$ 表示门客 $i$ 的智谋值（可能为负数）。

输出格式

输出一行一个整数，表示最大的智谋值之和。

输入输出样例 #1

输入：

5 3
0 10
1 5
1 6
2 3
2 4

输出：

21

样例 #1 解释： 树结构：

• 1(10) 是根。
• 1 的下属：2(5), 3(6)。
• 2 的下属：4(3), 5(4)。 需选 3 人。1 号必选。
• 方案A：选 {1, 2, 3}。分值 $10+5+6=21$。
• 方案B：选 {1, 2, 4}。分值 $10+5+3=18$。
• 方案C：选 {1, 2, 5}。分值 $10+5+4=19$。 最大值为 21。

输入输出样例 #2

输入：

6 4
0 100
1 -10
1 20
2 50
2 10
3 1000

输出：

1110

样例 #2 解释： 树结构：

• 1(100) -> 2(-10), 3(20)
• 2(-10) -> 4(50), 5(10)
• 3(20) -> 6(1000) 需选 4 人。
• 为了拿到最大值 6(1000)，必须选 3，必须选 1。
• 目前已选 {1, 3, 6}，人数 3，总分 $100+20+1000=1120$。
• 还差 1 人。
  • 只能选 2（因为4和5的上级2还没选，不能跳过2直接选4,5）。
• 最终选择 {1, 3, 6, 2}。
• 总分 $1120 + (-10) = 1110$。

数据范围

对于 $100\%$ 的数据：

• $1 \le K \le N \le 300$ （树形背包经典数据范围）
• $-1000 \le V_i \le 1000$
• 保证是一棵合法的树。

---

第三部分：题目分析与标准代码

1. 状态定义

这是一个分组背包模型。

• $dp[u][j]$：在以 $u$ 为根的子树中，恰好选择 $j$ 个节点（其中必须包含 $u$ 自己），所能获得的最大权值。

2. 状态转移

对于节点 $u$ 的每一个子节点 $v$： 我们将 $v$ 子树看作一组物品。这组物品可以选择拿 $1$ 个、$2$ 个 $\dots$ 直到 $size[v]$ 个。 我们要将子树 $v$ 的选法合并到 $u$ 的状态中。

$$dp[u][j] = \max_{0 \le k < j} (dp[u][j-k] + dp[v][k]) $$

• $j$：当前 $u$ 子树（包含已经合并过的其他子树）总共选多少人。倒序枚举。
• $k$：分给当前子节点 $v$ 的名额。

3. 复杂度优化（树形背包的 $O(N^2)$ 优化）

如果暴力枚举 $j$ 和 $k$ 到 $K$，复杂度是 $O(N \cdot K^2)$。 优化策略：

1. $j$ 的上限不需要到 $K$，只需要到 $size[u]$（当前已合并的子树大小）。
2. $k$ 的上限不需要到 $K$，只需要到 $size[v]$。 这样优化后，总复杂度可以证明为 $O(N^2)$。

4. 标准代码 (C++14)

/**
 * 题目：孟尝君的门客
 * 难度：GESP 6级 / 提高+
 * 算法：树形背包 DP
 */

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

using namespace std;

// 开启 IO 优化
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

const int MAXN = 305;
const int INF = 0x3f3f3f3f; // 足够大的数，代表不可达

vector<int> adj[MAXN];
int val[MAXN];
int sz[MAXN]; // 子树大小

// dp[u][j]: 以u为根的子树选j个(含u)的最大权值
int dp[MAXN][MAXN]; 
int N, K;

void dfs(int u) {
    // 1. 初始化
    sz[u] = 1;
    dp[u][1] = val[u]; // 选1个就是选自己

    // 2. 遍历子节点（分组背包）
    for (int v : adj[u]) {
        dfs(v);

        // 3. 状态转移（背包合并）
        // 倒序枚举当前背包容量 j
        // 优化：j 的上限是 min(K, sz[u] + sz[v])
        for (int j = min(K, sz[u] + sz[v]); j >= 2; --j) {
            
            // 枚举分给子树 v 的名额 k
            // k 的范围：1 到 sz[v] (v子树最多这么大)
            // 且 k < j (因为 u 自己至少占 1 个，留给 v 的最多 j-1)
            // 且 j-k <= sz[u] (留给 u 原本部分的不能超过 u 原本的大小)
            // 这里的 sz[u] 是指合并 v 之前的大小
            
            // 为了代码简洁，通常只写主要边界，依赖 dp 初始化的 -INF 来过滤非法状态
            for (int k = 1; k <= sz[v] && k < j; ++k) {
                if (dp[u][j-k] != -INF && dp[v][k] != -INF) {
                    dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);
                }
            }
        }
        // 合并完一个子节点后，更新 u 的大小
        sz[u] += sz[v];
    }
}

int main() {
    fast_io();

    if (!(cin >> N >> K)) return 0;

    int root = 0;
    // 初始化 DP 数组为 -INF
    for(int i=0; i<=N; i++) {
        for(int j=0; j<=K; j++) {
            dp[i][j] = -INF;
        }
    }

    for (int i = 1; i <= N; ++i) {
        int p;
        cin >> p >> val[i];
        if (p == 0) root = i;
        else adj[p].push_back(i);
    }

    dfs(root);

    // 题目保证一定有解吗？
    // 如果 K > N，或者树结构导致无法选 K 个，dp[root][K] 仍为 -INF
    // 但题目说 K <= N，且是一棵树，所以一定能选出 K 个
    cout << dp[root][K] << endl;

    return 0;
}

---

第四部分：数据生成器

生成 1.in ~ 10.in 及其对应标准答案。包含链状、随机、负权值等情况。

/**
 * GESP 6级 [孟尝君的门客] - 数据生成器
 */
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

// ------------------------------------------
// 标准解法函数 (生成 .out)
// ------------------------------------------
const int MAXN_S = 305;
const int INF_S = 1e9;
vector<int> adj_s[MAXN_S];
int val_s[MAXN_S];
int sz_s[MAXN_S];
int dp_s[MAXN_S][MAXN_S];

void dfs_solve(int u, int K) {
    sz_s[u] = 1;
    dp_s[u][1] = val_s[u];
    
    for (int v : adj_s[u]) {
        dfs_solve(v, K);
        // 这里的 sz_s[u] 是合并 v 之前的大小
        for (int j = min(K, sz_s[u] + sz_s[v]); j >= 2; --j) {
            for (int k = 1; k <= sz_s[v] && k < j; ++k) {
                if (dp_s[u][j-k] > -INF_S && dp_s[v][k] > -INF_S) {
                    dp_s[u][j] = max(dp_s[u][j], dp_s[u][j-k] + dp_s[v][k]);
                }
            }
        }
        sz_s[u] += sz_s[v];
    }
}

int solve(int N, int K, int root, const vector<pair<int, int>>& nodes, const vector<pair<int, int>>& edges) {
    for(int i=1; i<=N; i++) {
        adj_s[i].clear();
        for(int j=0; j<=K; j++) dp_s[i][j] = -INF_S;
    }
    
    for(int i=1; i<=N; i++) val_s[i] = nodes[i-1].second;
    for(auto& e : edges) adj_s[e.first].push_back(e.second);

    dfs_solve(root, K);
    return dp_s[root][K];
}

// 辅助函数
int randRange(int min, int max) {
    return rand() % (max - min + 1) + min;
}

int main() {
    srand(time(0));
    
    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N, K;
        
        // 构造测试点
        if (i == 1) { // 样例1
            N = 5; K = 3;
        } else if (i == 2) { // 样例2
            N = 6; K = 4;
        } else if (i == 3) { // 链状
            N = 20; K = 10;
        } else if (i == 4) { // 菊花图
            N = 20; K = 5;
        } else if (i <= 7) { // 小规模随机
            N = randRange(30, 50);
            K = randRange(1, N);
        } else { // 大规模随机
            N = randRange(200, 300);
            K = randRange(1, N);
        }

        vector<pair<int, int>> nodes(N);
        vector<pair<int, int>> edges;
        int root = 1;

        // 生成树结构：i 的父亲在 1~i-1 中选，保证 1 是根
        vector<int> p(N + 1, 0);
        for(int k=2; k<=N; k++) {
            if(i == 3) p[k] = k - 1; // 链状
            else if(i == 4) p[k] = 1; // 菊花
            else p[k] = randRange(1, k - 1); // 随机
            
            edges.push_back({p[k], k});
        }

        // 生成权值
        for(int k=1; k<=N; k++) {
            if (i == 1 && k <= 5) { // 样例1 数据
                int v[] = {0, 10, 5, 6, 3, 4}; 
                nodes[k-1] = {p[k], v[k]};
            } else if (i == 2 && k <= 6) { // 样例2 数据
                int v[] = {0, 100, -10, 20, 50, 10, 1000};
                nodes[k-1] = {p[k], v[k]};
            } else {
                // 随机权值，包含负数
                nodes[k-1] = {p[k], randRange(-100, 100)};
            }
        }

        // 写入输入
        fin << N << " " << K << endl;
        for (int k=0; k<N; k++) {
            fin << nodes[k].first << " " << nodes[k].second << endl;
        }

        // 写入输出
        fout << solve(N, K, root, nodes, edges) << endl;

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    cout << "Done!" << endl;
    return 0;
}