「一本通 5.2 例 1」二叉苹果树

题目描述

有一棵 $N$ 个节点的二叉苹果树，树根为 $1$ ，非叶节点恰有两个子节点。每条树枝上有一个非负整数苹果数。给定要保留的树枝数 $Q$ ，求能保留的最多苹果数。

输入第一行是 $N,Q$ ，接下来 $N-1$ 行每行给出一条树枝两端的节点编号和苹果数。输出一行，表示最多能留住的苹果数。

数据范围： $1 \le Q \le N \le 100$ ，每根树枝苹果数不超过 $30000$ 。

思路

设 $f(u,k)$ 表示以 $u$ 为根的子树保留 $k$ 条边的最大苹果数。保留 $k$ 条边时要么只走左（消耗 1 条边），要么只走右（消耗 1 条边），要么两边都走并枚举左右子树分别分配 $i$ 和 $k-2-i$ 条边。从根节点记忆化搜索得 $f(1,Q)$ 。

参考代码

Python 版：

python

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#!/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-09-30 19:30
# update_at: 2026-09-30 19:30

import sys
from functools import cache


def solve() -> None:
    data = list(map(int, sys.stdin.read().split()))
    if not data:
        return
    it = iter(data)
    n, q = next(it), next(it)

    adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v, w = next(it), next(it), next(it)
        adj[u].append((v, w))
        adj[v].append((u, w))

    # 构建二叉树有向结构：children[u] = [(v1, w1), (v2, w2)]
    children: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    visited = [False] * (n + 1)
    visited[1] = True
    queue = [1]
    for u in queue:
        for v, w in adj[u]:
            if not visited[v]:
                visited[v] = True
                children[u].append((v, w))
                queue.append(v)

    # 记忆化搜索：dfs(u, k) 表示在以 u 为根的子树中保留 k 条边能获得的最大苹果数
    @cache
    def dfs(u: int, k: int) -> int:
        """在以 u 为根的子树内保留 k 条边的最大权值和。"""
        if k == 0 or not children[u]:
            return 0

        # 根据题意分叉一定是两叉或 0 叉（叶子）
        (l, wl), (r, wr) = children[u]

        # 分三种情况：只选左、只选右、两边分配
        return max(
            dfs(l, k - 1) + wl,
            dfs(r, k - 1) + wr,
            max(
                (dfs(l, i) + wl + dfs(r, k - 2 - i) + wr for i in range(k - 1)),
                default=0,
            ),
        )

    print(dfs(1, q))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102/**
 * 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-06 00:48
 * update_at: 2026-10-06 00:48
 */

#include <cstdio>
#include <vector>
#include <utility>
using namespace std;

typedef long long ll;

const int MAXN = 105;
const int MAXQ = 105;

int n, q;

// children[u][0] = (左子节点, 边权); children[u][1] = (右子节点, 边权)
// 叶子节点对应的 children 为空
vector<pair<int, int> > children[MAXN];

// dp[u][k] 表示以 u 为根的子树中保留 k 条边能获得的最大苹果数
int dp[MAXN][MAXQ];

// 构建以根节点 1 为起点的有向二叉树
void build_tree() {
    // 用邻接表读取无向边
    vector<pair<int, int> > adj[MAXN];
    for (int i = 1; i <= n - 1; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
    }

    // 从根节点 1 开始 BFS，把子节点加入 children
    int queue[MAXN];
    int head = 0, tail = 0;
    bool visited[MAXN] = {false};
    visited[1] = true;
    queue[tail++] = 1;
    while (head < tail) {
        int u = queue[head++];
        for (int i = 0; i < (int)adj[u].size(); i++) {
            int v = adj[u][i].first;
            int w = adj[u][i].second;
            if (!visited[v]) {
                visited[v] = true;
                children[u].push_back(make_pair(v, w));
                queue[tail++] = v;
            }
        }
    }
}

// 树形背包 DFS：计算以 u 为根的子树保留 k 条边的最大权值
int dfs(int u, int k) {
    if (k == 0 || children[u].empty()) {
        return 0;
    }
    if (dp[u][k] != -1) {
        return dp[u][k];
    }

    int l = children[u][0].first;
    int wl = children[u][0].second;
    int r = children[u][1].first;
    int wr = children[u][1].second;

    int res = 0;

    // 只保留左子树：必须选边 (u, l)
    res = max(res, dfs(l, k - 1) + wl);
    // 只保留右子树：必须选边 (u, r)
    res = max(res, dfs(r, k - 1) + wr);

    // 左右子树都保留：两条边必选，剩余 k-2 条边在左右子树之间分配
    for (int i = 0; i <= k - 2; i++) {
        res = max(res, dfs(l, i) + wl + dfs(r, k - 2 - i) + wr);
    }

    dp[u][k] = res;
    return res;
}

int main() {
    scanf("%d %d", &n, &q);
    build_tree();

    // 初始化记忆化数组
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= q; j++) {
            dp[i][j] = -1;
        }
    }

    printf("%d\n", dfs(1, q));
    return 0;
}

「一本通 5.2 例 1」二叉苹果树

目录

题目描述

思路

参考代码