P2015 二叉苹果树 · 习题解析｜信息学奥赛算法练功房

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P2015，日期见页头。两边不一致时信原站。

题目描述

有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点）。

这棵树共有 N 个结点（叶子点或者树枝分叉点），编号为 1 ~ N，树根编号一定是 1。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一棵有 4 个树枝的树：

现在这棵树枝条太多了，需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量，求出最多能留住多少苹果。

留住一个苹果的定义为苹果所在枝条直接与根相连或通过其他枝条间接与根相连。

输入格式

第一行 2 个整数 N 和 Q，分别表示树的结点数，和要保留的树枝数量。

接下来 N−1 行，每行 3 个整数，描述一根树枝的信息：前 2 个数是它连接的结点的编号，第 3 个数是这根树枝上苹果的数量。

输出格式

一个数，最多能留住的苹果的数量。

说明/提示

1 ≤ Q < N ≤ 100，每根树枝上的苹果 ≤ 3 × 10⁴。

输入输出样例

输入

输出

五个点、四根枝。保留 2 根：留 1—3（1 个苹果）和 3—5（20 个）⇒ 21。

⚠ 注意为什么不能留那两根 20（2—3 和 3—5）：它们都要靠 1—3 才连得到根，一共就成了三根枝，超了。「保留」这个动作是有形状的，这正是这道题的全部难点。

1★ 第一版：把苹果最多的 Q 根枝留下

p2015Greedy.cpp✗ 第一版：按苹果数排序，取前 Q 根

// ✗ P2015 第一版：把苹果最多的 Q 条枝留下
//
// ★ 它错在**连通性**：留下来的枝条必须和根连成一片，
//    半空中吊着一条挂满苹果的枝，是留不住的。
// ⇒ 它解的是一个**放宽了的问题** ⇒ 恒 ≥ 正解。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if (!(cin >> n >> q)) return 0;
    vector<int> w;
    for (int i = 1; i < n; i++) { int a, b, c; cin >> a >> b >> c; w.push_back(c); }
    sort(w.rbegin(), w.rend());
    long long sum = 0;
    for (int i = 0; i < q && i < (int)w.size(); i++) sum += w[i];
    cout << sum << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★ 又一次「放宽了的问题 ⇒ 恒 ≥ 正解」

半空中吊着一根挂满苹果的枝，是留不住的 —— 留下来的枝必须和根连成一片。这个贪心把这条要求扔了 ⇒ 它解的是一个放宽了的问题 ⇒ 恒 ≥ 正解。


它 ≥ 正解	★ 300 / 300
300 轮被抓	205
错的时候平均多报	24.52%

★ 官方样例当场挡住它（40 vs 21）。

2★★ 关键的一步：树形背包 —— 每个儿子是一件「重量可选」的物品

★ f[u][j] = 在 u 的子树里保留 j 条枝，最多留住多少苹果

    f[u][j] = max over k:  f[u][j-k-1] + f[v][k] + w(u, v)
                                 ^^^^ 那个 -1 就是 (u,v) 这根枝自己

三件事一起看才讲得通：

每个儿子 v 是一件物品，但它的「重量」不是定死的 —— 在它那边留 0, 1, 2, … 条枝都行，所以要在 k 上枚举一遍（这就是第 25 章的分组背包：一个儿子是一组）；
(u, v) 这根枝本身也要占一个名额 —— 而且必须先留它，v 那边的枝才连得到根。这就是那个 −1；
j 要倒着枚举，理由和 01 背包一维完全一样：正着枚举时 f[u][j−k−1] 可能已经用过这个儿子了。 ⚠ 而第 23 章 P1877 提醒过：「倒序」本身也有前提（转移必须单向），这道题的转移只从小容量流向大容量，所以倒序在这儿站得住。

p2015.cpp★ 这一版就能 AC

// P2015 二叉苹果树 —— 正解：树形背包（树形 DP × 01 背包），O(n²)
//
//   f[u][j] = 在 u 的子树里**保留 j 条树枝**时，最多能留住多少苹果
//
// 每个儿子 v 是一件「物品」，但它的重量不是定死的 —— 你可以在它那边留 0 条、1 条、…… 条枝。
// 而**连接 u 和 v 的那条枝**本身也要占一个名额，且必须先留它，v 那边才连得上根：
//
//   f[u][j] = max over k:  f[u][j-k-1] + f[v][k] + w(u, v)
//                              ^^^^^ 那个 -1 就是 (u,v) 这条枝自己
//
// ⚠ 和 01 背包一维一样，**j 必须倒着枚举** —— 否则同一个儿子会被用第二次。
// ⚠ 树是无向给的（`a b 苹果数`），要先从 1 号点 DFS 定向。

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

const int MAXN = 105;
int n, q;
struct E { int to, w; };
vector<E> adj[MAXN];
int f[MAXN][MAXN], sz[MAXN];

void dfs(int u, int fa) {
    sz[u] = 0;
    for (auto& e : adj[u]) {
        int v = e.to;
        if (v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v] + 1;                              // 子树里的枝条数
        for (int j = min(sz[u], q); j >= 1; j--)         // ← 倒序
            for (int k = 0; k <= min(sz[v], j - 1); k++)
                f[u][j] = max(f[u][j], f[u][j - k - 1] + f[v][k] + e.w);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> q)) return 0;
    for (int i = 1; i < n; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    dfs(1, 0);
    cout << f[1][q] << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

3★★★ 第二个错法：忘了给那根枝留名额 —— 而它两个方向都错

p2015NoEdge.cpp✗ f[u][j-k] —— 少了那个 -1

// ✗ P2015：忘了给「u 到 v 那条枝」自己留一个名额
//
//   f[u][j] = max(f[u][j-k] + f[v][k] + w)      ← 少了那个 -1
//
// ⚠⚠ 我起初在这儿写的是「它以为接一个儿子是免费的 ⇒ 多留枝 ⇒ **恒 ≥ 正解**」。
//     **实测把这句话打回来了：300 轮里只有 242 轮 ≥，还有 58 轮比正解小。**
//     最小反例只要三个点：`3 2 / 1 2 20 / 1 3 29` —— 正解 49，它只给 29。
//     道理是：不占名额 ⇒ 所有方案都被塞进了**小的 j** 里，
//     于是 f[1][Q] 这一格反而空空如也。
// ⇒ ★★★ 它**既凭空造状态、也弄丢合法状态**，两个方向都错。
//     （和第 23 章「一维就地覆盖只会多算」那次是同一种打脸：
//      **「这个 bug 只会往一个方向错」这句话必须量，不能推。**）

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

const int MAXN = 105;
int n, q;
struct E { int to, w; };
vector<E> adj[MAXN];
int f[MAXN][MAXN], sz[MAXN];

void dfs(int u, int fa) {
    sz[u] = 0;
    for (auto& e : adj[u]) {
        int v = e.to;
        if (v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v] + 1;
        for (int j = min(sz[u], q); j >= 1; j--)
            for (int k = 0; k <= min(sz[v], j); k++)
                f[u][j] = max(f[u][j], f[u][j - k] + f[v][k] + e.w);   // ← 这里
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> q)) return 0;
    for (int i = 1; i < n; i++) { int a, b, w; cin >> a >> b >> w; adj[a].push_back({b, w}); adj[b].push_back({a, w}); }
    dfs(1, 0);
    cout << f[1][q] << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

⚠⚠ 这一页最值钱的一条：我的草稿被实测打回来了

草稿里我写的是：「它以为接一个儿子是免费的 ⇒ 它会多留枝 ⇒ 恒 ≥ 正解」。听着很顺。

实测不是这样：


它 ≥ 正解	242 / 300（不是 300）
★ 它比正解小的轮数	58 / 300
300 轮被抓	297

最小反例只要三个点（3 2 / 1 2 20 / 1 3 29）：正解 49，它只给 29。道理是：不占名额 ⇒ 所有方案都被塞进了小的 j 里，于是我们真正要读的 f[1][Q] 那一格反而空空如也。

⇒ ★★★ 它既凭空造状态、也弄丢合法状态。 这和第 23 章那次「一维就地覆盖只会多算」是同一种打脸： 「这个 bug 只会往一个方向错」是必须量出来的，不能推。

4★ 第三个错法：容量正序（样例放过了它）

p2015Fwd.cpp✗ j 从小到大枚举

// ✗ P2015：容量 j 写成了正序
//
// ⚠ 这和第 23 章 01 背包一维那条「必须倒序」是同一件事：
//    正序时 f[u][j-k-1] 可能**已经用过这个儿子了**，于是同一个儿子被接了第二次。
// ⇒ 它凭空造出了根本不存在的方案 ⇒ 恒 ≥ 正解。
// ★ 而[第 23 章 P1877](/sol/p1877/) 那一页说过：「倒序」本身也是有前提的（转移必须单向）——
//    这道题的转移只从小容量流向大容量，所以倒序在这儿是对的。

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

const int MAXN = 105;
int n, q;
struct E { int to, w; };
vector<E> adj[MAXN];
int f[MAXN][MAXN], sz[MAXN];

void dfs(int u, int fa) {
    sz[u] = 0;
    for (auto& e : adj[u]) {
        int v = e.to;
        if (v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v] + 1;
        for (int j = 1; j <= min(sz[u], q); j++)          // ← 正序
            for (int k = 0; k <= min(sz[v], j - 1); k++)
                f[u][j] = max(f[u][j], f[u][j - k - 1] + f[v][k] + e.w);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> q)) return 0;
    for (int i = 1; i < n; i++) { int a, b, w; cin >> a >> b >> w; adj[a].push_back({b, w}); adj[b].push_back({a, w}); }
    dfs(1, 0);
    cout << f[1][q] << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

同一个儿子被接了第二次 ⇒ 凭空多出根本不存在的方案 ⇒ 恒 ≥ 正解（300 / 300），被抓 237 / 300。

⚠ 而官方样例原样放过它（都输出 21）。 ⇒ 这一页三个错法正好把那条规律演了一遍： 样例挡住的两个（贪心、忘了 −1）在样例上就露了馅，放过的那个是「偶尔才错」的 —— 而真正让你 WA 在第 7 个点上的，恰恰是后一种。

5★★ 题面那句「一定是分二叉」，是情报、命门，还是噪声？

★ 判据是同一个动作：造一档违反它的数据，看有没有任何一版的行为变了

本页默认档造的是一般的随机树（有的点只有一个儿子）——故意违反那句话。再造一档真·二叉（每个非叶子恰好两个儿子）对比：

各 300 轮	一般随机树（违反题面）	真·二叉（题面保证）
正解 vs 暴力不一致	0	0
贪心被抓	205	209
忘了 `−1` 被抓	297	296
容量正序被抓	237	246

⇒ 没有任何一版的行为变了 ⇒ 按第 12 章那套三分法，那句话是噪声（对我们的算法而言）—— 它只是在描述这道题的背景，树形背包对任何形状的树都成立。

★ 好处是实打实的：生成器不必费劲去满足它，反而多覆盖了「只有一个儿子」这种形状。

6★★★ 「子树里最多 sz 条枝」这个上界，值多少？

内层那两句 min(sz[u], q) 和 min(sz[v], j−1) 是树形背包的招牌 —— 它们把看着像 O(nQ²) 的东西压成了 O(n²)。把转移次数数出来（顶格 n = 100、Q = 99）：

形状	带 `sz` 上界	不带	省了
随机树	10 200	490 050	★ 48.04 倍
一条链	166 650	490 050	2.94 倍

⚠ 但在这道题上，这个优化一分钱都不值

n ≤ 100 ⇒ 就算一次不省，49 万次转移也是眨眼的事。 ⇒ 又一次「一个优化值多少倍，主语是数据和规模」：这个上界真正值钱是在 n = 10⁵ 的树形背包题里，不是这儿。

★ 而两行的倍数差 16 倍（48.04 vs 2.94）本身是有意思的：链上每个 sz[u] 都很大，上界几乎卡不住；随机树又矮又宽，它卡得很紧。 「这个剪枝省多少」永远要连着形状一起说。

7★ 参照物、规模和上界


300 轮：正解 vs 枚举保留哪 `Q` 条枝	★ 不一致 0 轮
顶格 `n = 100`、每根枝 `≤ 3 × 10⁴` ⇒ 答案上界	2 970 000 ⇒ `int` 够

参照物枚举 2ⁿ⁻¹ 个枝条子集，逐个检查它们能不能从根走到 —— 和第 ① 步那个贪心的区别只有一句话，而那句话就是这道题。

p2015Brute.cpp参照物：枚举保留哪 Q 条枝（300 轮不一致 0 轮）

8度量程序和生成器

p2015Count.cpp度量程序（本页所有数字都出自它）

p2015Gen.cpp数据生成器

9一页纸


★★ 关键的一步	`f[u][j−k−1] + f[v][k] + w` —— 每个儿子是一组，那根枝自己也占一个名额
★ 第一版	按苹果数取前 `Q` 根 ⇒ 放宽了连通性 ⇒ 恒 ≥ 正解，被抓 205/300，平均多报 24.52%
★★★ 忘了那个 `−1`	⚠ 草稿说「恒 ≥」，实测只有 242/300 —— 还有 58 轮比正解小，最小反例三个点
★ 容量正序	恒 ≥ 正解，被抓 237/300；⚠ 官方样例放过了它
★★ 「一定是分二叉」	造一档违反它的数据 ⇒ 四行数字全没变 ⇒ 它是噪声
★★★ `sz` 上界值多少	随机树省 48.04 倍、链只省 2.94 倍；⚠ 而 `n ≤ 100` ⇒ 这道题上一分钱不值
参照物	枚举保留哪 `Q` 条枝＋检查连不连得到根；300 轮不一致 0 轮
规模	答案上界 2 970 000 ⇒ `int` 够

洛谷 P2015 二叉苹果树

0题目原文（本地存了一份）

输入

输出

1★ 第一版：把苹果最多的 Q 根枝留下

2★★ 关键的一步：树形背包 —— 每个儿子是一件「重量可选」的物品

3★★★ 第二个错法：忘了给那根枝留名额 —— 而它两个方向都错

4★ 第三个错法：容量正序（样例放过了它）

5★★ 题面那句「一定是分二叉」，是情报、命门，还是噪声？

6★★★ 「子树里最多 sz 条枝」这个上界，值多少？

7★ 参照物、规模和上界

8度量程序和生成器

9一页纸