你好！我是你的OI教练。欢迎来到树形DP的第四站——树上背包（Tree Knapsack）。

这道题是 P2014《选课》的简化版，也是树上背包最基础的模型。相比之前的题，这道题的难点在于：我们不仅要决定“选不选”，还要决定“选多少”。

来，准备好草稿纸，我们把这个背包背到树上去。

---

第一部分：思路提示

1. 麻烦的边权（转化思想）

• 题目里的苹果是长在“树枝”（边）上的，而我们之前的DP通常是处理“节点”的权值。
• 技巧：除了根节点外，每个节点都有唯一的一条入边（来自父亲）。
• 我们可以把边上的苹果数量，直接移到这条边连接的子节点身上。
• 例如：边 $(u, v)$ 上有 10 个苹果，我们就可以认为节点 $v$ 的价值是 10。选了节点 $v$（及其入边），就得到了 10 个苹果。

2. 状态定义（背包的影子）

• 这是一个有依赖的背包问题：要想选子节点（下面的树枝），必须先选父节点（上面的树枝）。
• 我们需要一个维度来记录“背包容量”（即题目要求的 $Q$ 根树枝）。
• $dp[u][j]$：表示在以 $u$ 为根的子树中，保留 $j$ 根树枝（或者说选了 $j$ 个节点，不含 $u$ 上面的边），能得到的最大苹果数量。

3. 状态转移（分组背包）

• 想象一下，节点 $u$ 是一个组长。他有两个部下（左儿子 $L$ 和右儿子 $R$）。
• 现在上级给 $u$ 分配了 $j$ 个名额（树枝数）。
• $u$ 需要把这 $j$ 个名额分配给 $L$ 和 $R$。
  • 给 $L$ 分配 $k$ 个？那么给 $R$ 就剩下 $j - k$ 个了吗？
  • 注意：如果要让 $L$ 的子树有资格分名额，必须先消耗 1 个名额把 $u$ 和 $L$ 连起来！
  • 所以，如果 $L$ 子树分到了 $k$ 个名额（包括连接 $u-L$ 的那根），那么 $L$ 内部实际能用的名额是 $k-1$。

4. 泛化为多叉树（通用解法）

• 虽然题目说是“二叉”，但其实我们可以把它当成普通树来做，用DFS + 分组背包的思路。
• 对于 $u$ 的每一个子节点 $v$：
  • 我们枚举分给 $v$ 的树枝数 $k$（$0 \le k < j$）。
  • $u$ 剩下的树枝数就是 $j - k - 1$（那个 $1$ 是连接 $u$ 和 $v$ 的边）。
  • 这就像在背包问题中，枚举这个“物品组”（子树）选多大的体积。

---

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

1. 邻接表建图：注意题目给的是无向边，要建双向边，DFS 时用 fa 避免死循环。
2. 树形 DP + 背包：
   • 这是 $O(N^3)$ 的经典模型（当然可以优化到 $O(N^2)$，但在 $N=100$ 时无所谓）。
   • 外层循环枚举背包容量（倒序！），内层循环枚举给子树分配的体积。
3. 边权转点权：将边的权重存储在结构体中，DFS 访问子节点时，将边权传给子节点当作价值。

---

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

画图模拟：

假设有一小部分树结构：

      u
     /
    v (边权 w=10)

我们想算 $dp[u][...]$。

1. 初始化 $dp[u][0] = 0$ (给0根树枝，当然是0个苹果)。 其他 $dp[u][j]$ 初始化为 0。

2. 遍历子节点 v 假设 $v$ 的子树（包括 $v$ 自己）已经算好了：

• $dp[v][0] = 0$
• $dp[v][1] = 20$ (v下面还有个厉害的边)

现在我们要更新 $u$ 的状态。假设 $u$ 总共有 $j=2$ 个名额。 我们要决定：切给 $v$ 多少名额？

• 方案 A：不带 $v$ 玩

  • 给 $v$ 分配 -1 个名额（不可能），即连 $u-v$ 这根线都剪断。
  • 收益：$dp[u][2]$ (原来的值)。

• 方案 B：给 $v$ 分配 1 个名额

  • 这 1 个名额必须用来连接 $u-v$。
  • $v$ 自己手里剩 $1-1=0$ 个名额。
  • 收益：$dp[u][2-1] + dp[v][0] + 10$。
  • ($u$ 剩下的1个名额的价值) + ($v$ 用0个名额的价值) + (连接边 $w=10$)。

• 方案 C：给 $v$ 分配 2 个名额

  • 1 个连接 $u-v$，1 个给 $v$ 内部用。
  • 收益：$dp[u][2-2] + dp[v][1] + 10$。
  • ($u$ 剩下的0个名额) + ($v$ 用1个名额的价值) + (连接边 $w=10$)。

通用方程推导：

$$dp[u][j] = \max(dp[u][j], \quad dp[u][j - k - 1] + dp[v][k] + w_{uv}) $$

• $j$：当前 $u$ 拥有的总容量（从 $Q$ 到 1 倒序枚举）。
• $k$：分给子树 $v$ 内部的容量（从 $0$ 到 $j-1$ 枚举）。
• $1$：连接 $u$ 和 $v$ 的那条边，必须消耗 1 个容量。
• $w_{uv}$：这条边的苹果数。

---

第四部分：题解标准代码 (C++14)

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

using namespace std;

const int MAXN = 105;

// 结构体存边
struct Edge {
    int to;
    int weight;
};

vector<Edge> adj[MAXN];
// dp[u][j] 表示以 u 为根的子树，保留 j 条边能获得的最大苹果数
int dp[MAXN][MAXN];
int n, q;

void dfs(int u, int fa) {
    // 初始化：不需要做特别的初始化，全局默认为0即可
    // dp[u][0] = 0 是天然成立的
    
    // 遍历每一个子节点（相当于背包问题中的“物品组”）
    for (auto& edge : adj[u]) {
        int v = edge.to;
        int w = edge.weight;
        
        if (v == fa) continue; // 防止回头
        
        dfs(v, u); // 先递归把子树算好
        
        // 树上背包的核心状态转移
        // 1. 外层循环：倒序枚举当前 u 的背包容量 j
        // 为什么倒序？和 0/1 背包一样，防止同一个子树被重复累加
        for (int j = q; j >= 1; j--) {
            // 2. 内层循环：枚举给子树 v 分配多少条边 (k)
            // k 的范围：
            //   - 至少 0 条
            //   - 最多 j - 1 条 (因为必须留 1 条给 u-v 这根主连线)
            for (int k = 0; k <= j - 1; k++) {
                // dp[u][j] = max(不选这个分配方案, 选这个方案)
                // 方案价值 = u还剩(j-k-1)容量时的价值 + v子树用k容量的价值 + 连接边的价值w
                dp[u][j] = max(dp[u][j], dp[u][j - k - 1] + dp[v][k] + w);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    if (!(cin >> n >> q)) return 0;
    
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    
    dfs(1, 0); // 从根节点 1 开始 DFS
    
    cout << dp[1][q] << endl;
    
    return 0;
}

---

第五部分：数据生成器 (Data Generator)

这个生成器会生成符合题目要求的二叉树（或类二叉树），并涵盖各种 $Q$ 的情况。

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <string>
#include <random>
#include <chrono>

using namespace std;

// ================= 核心解法 (用于生成 .out) =================
const int MAX_SOLVE_N = 105;
struct Edge { int to, w; };
vector<Edge> adj[MAX_SOLVE_N];
int dp[MAX_SOLVE_N][MAX_SOLVE_N];

void solve_dfs(int u, int fa, int q) {
    for (auto& e : adj[u]) {
        int v = e.to;
        if (v == fa) continue;
        solve_dfs(v, u, q);
        for (int j = q; j >= 1; j--) {
            for (int k = 0; k <= j - 1; k++) {
                dp[u][j] = max(dp[u][j], dp[u][j - k - 1] + dp[v][k] + e.w);
            }
        }
    }
}

int solve(int n, int q, const vector<tuple<int,int,int>>& edges) {
    for(int i=0; i<=n; ++i) {
        adj[i].clear();
        for(int j=0; j<=q; ++j) dp[i][j] = 0;
    }
    for(auto& e : edges) {
        adj[get<0>(e)].push_back({get<1>(e), get<2>(e)});
        adj[get<1>(e)].push_back({get<0>(e), get<2>(e)});
    }
    solve_dfs(1, 0, q);
    return dp[1][q];
}

// ================= 数据生成工具 =================

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int random_int(int l, int r) {
    uniform_int_distribution<int> dist(l, r);
    return dist(rng);
}

// 生成数据
void generate_case(int case_id, int n, string type) {
    string in_file = to_string(case_id) + ".in";
    string out_file = to_string(case_id) + ".out";

    ofstream fout(in_file);
    
    // Q 的范围：1 到 N-1
    int q;
    if (case_id == 1) q = 1; // 最小 Q
    else if (case_id == 2) q = n - 1; // 最大 Q (全选)
    else q = random_int(1, n - 1);

    fout << n << " " << q << endl;

    vector<tuple<int, int, int>> edges;
    vector<int> p(n + 1);
    for (int i = 1; i <= n; i++) p[i] = i;

    // 构造树
    // 为了符合题目“二叉树”的描述，我们尽量构造每个节点最多2个子节点
    // 但实际上标准代码适用于多叉树，这里严格模拟二叉结构
    // 策略：维护一个可用父节点池
    vector<int> nodes;
    for(int i=2; i<=n; ++i) nodes.push_back(i);
    shuffle(nodes.begin(), nodes.end(), rng);

    vector<int> parents; 
    parents.push_back(1); // 根节点
    vector<int> child_count(n + 1, 0);

    int node_idx = 0;
    while(node_idx < nodes.size()) {
        // 随机选一个还没满2个儿子的父节点
        int p_idx = random_int(0, parents.size() - 1);
        int u = parents[p_idx];

        if (child_count[u] < 2) {
            int v = nodes[node_idx++];
            int w = random_int(1, 30000); // 苹果数量
            edges.push_back(make_tuple(u, v, w));
            fout << u << " " << v << " " << w << endl;
            
            child_count[u]++;
            parents.push_back(v); // 新节点也可以当爹
        } else {
            // 这个爹满了，从池子里移除，换一个爹
            parents.erase(parents.begin() + p_idx);
            // 这里为了简化，如果满了就continue，下次循环再选
            // 实际上 parents移除后可以保证效率
        }
    }

    fout.close();

    // 生成答案
    int ans = solve(n, q, edges);
    ofstream f_ans(out_file);
    f_ans << ans << endl;
    f_ans.close();

    cout << "Case " << case_id << ": N=" << n << " Q=" << q << " Ans=" << ans << endl;
}

int main() {
    // 题目约束 N <= 100
    // Test 1-3: 小数据
    generate_case(1, 5, "random"); // Q=1
    generate_case(2, 5, "random"); // Q=N-1
    generate_case(3, 10, "random");

    // Test 4-6: 中等数据
    generate_case(4, 30, "random");
    generate_case(5, 50, "random");
    generate_case(6, 50, "random");

    // Test 7-10: 满数据 (N=100)
    generate_case(7, 99, "random"); // 奇数节点容易构成满二叉树
    generate_case(8, 100, "random");
    generate_case(9, 100, "random");
    generate_case(10, 100, "random");

    cout << "All cases generated." << endl;
    return 0;
}