二叉苹果树

形式化题目

给定一棵包含 $N$ 个结点的带权无向树，结点编号为 $1 \sim N$ ，以 $1$ 号结点为根。每条边连接两个结点，并带有非负权值（表示枝条上的苹果数）。

要求在树中保留恰好 $Q$ 条边，使得：

所有被保留的边构成的子图与根结点 $1$ 连通（即任意保留边均可沿保留边到达根结点）；
被保留边的权值之和最大。

求所能获得的最大权值和。

暴力解法

思路

树上共有 $N-1$ 条边。最直接的朴素做法是通过深度优先搜索枚举所有边的选择状态：

每条边有两种决策：保留（ $1$ ）或不保留（ $0$ ）；
递归到底后，统计已选边的数量是否恰好为 $Q$ ；
若恰好为 $Q$ 条边，从根结点 $1$ 出发进行广度优先搜索（BFS），检查是否恰好可以访问到所有的 $Q$ 条边（确保连通性）；
连通性校验通过后，累计所有连通保留边的权值之和，并更新全局最大值。

代码

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
103
104
105
106
107
108
109
110
111
112
113
114
115#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;

struct Edge {
    int u, v, w;
};

int n, q_need;
Edge edges[MAXN];
vector<pair<int, int> > g[MAXN];
int chosen[MAXN]; // chosen[i] = 0/1，表示第 i 条边不保留/保留
int ans;

int calc_chosen_count() {
    int cnt = 0;
    for (int i = 1; i < n; i++) {
        if (chosen[i] == 1) cnt++;
    }
    return cnt;
}

bool check() {
    if (calc_chosen_count() != q_need) {
        return false;
    }

    vector<int> vis(n + 1, 0);
    queue<int> q;
    q.push(1);
    vis[1] = 1;
    int connected_edges = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (size_t i = 0; i < g[u].size(); i++) {
            int id = g[u][i].second;
            int v = g[u][i].first;
            if (chosen[id] == 0 || vis[v]) {
                continue;
            }
            vis[v] = 1;
            connected_edges++;
            q.push(v);
        }
    }

    return connected_edges == q_need;
}

int calc_answer() {
    vector<int> vis(n + 1, 0);
    queue<int> q;
    q.push(1);
    vis[1] = 1;
    int sum = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (size_t i = 0; i < g[u].size(); i++) {
            int id = g[u][i].second;
            int v = g[u][i].first;
            if (chosen[id] == 0 || vis[v]) {
                continue;
            }
            vis[v] = 1;
            sum += edges[id].w;
            q.push(v);
        }
    }

    return sum;
}

void dfs_choose(int dep) {
    if (dep == n) {
        if (check()) {
            int value = calc_answer();
            if (ans < value) ans = value;
        }
        return;
    }

    // 第 dep 条边的 01 选择：0 不保留，1 保留。
    for (int i = 0; i <= 1; i++) {
        chosen[dep] = i;
        dfs_choose(dep + 1);
    }
}

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

    // brute.cpp：枚举保留哪些边，再检查这些边是否仍然和根连通。
    cin >> n >> q_need;
    for (int i = 1; i <= n; i++) {
        g[i].clear();
    }

    for (int i = 1; i < n; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        g[edges[i].u].push_back({edges[i].v, i});
        g[edges[i].v].push_back({edges[i].u, i});
        chosen[i] = 0;
    }

    ans = 0;
    dfs_choose(1);
    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度：共有 $N-1$ 条边，枚举子集的状态空间为 $O(2^{N-1})$ 。每个叶子节点进行一次 BFS 连通性检查与权值求和，耗时 $O(N)$ 。总时间复杂度为 $O(N \cdot 2^N)$ 。
空间复杂度：存储邻接表与搜索栈深度均为 $O(N)$ 。

瓶颈

当 $N$ 增大时（例如本题 $N \le 100$ ）， $2^{N-1}$ 的搜索规模会导致指数级爆炸。暴力做法没有利用树的无环与子树独立性：子树中哪些边能连通到根，完全取决于连向该子树的父边是否被保留；子树内部的边数分配只依赖于分配给它的配额，具有明显的最优子结构和无后效性。

正解

思路

将树以 $1$ 号节点为根进行有向化。

1. 状态定义

定义 $dp[u][j]$ 表示：在以 $u$ 为根的子树中保留 $j$ 条边，且这 $j$ 条边均能通过 $u$ 连回根节点时，能获得的最大苹果数。

2. 状态转移与树上分组背包

对于节点 $u$ 的某个儿子节点 $v$ （边权为 $w(u, v)$ ）：

若不在 $v$ 的子树中保留任何边，则无需保留边 $(u, v)$ ；
若在 $v$ 的子树中保留 $take$ 条边（ $take \ge 0$ ），由于这 $take$ 条边必须连通到根，边 $(u, v)$ 必须被同时保留。因此，消耗的总边数增加 $take + 1$ ，收益增加 $dp[v][take] + w(u, v)$ 。

我们将节点 $u$ 的每一个子节点 $v$ 视作一个分组背包中的「组」，在子树 $v$ 中保留的边数 $take$ 视作该组内的互斥物品选项：

dp[u][used + take + 1] = \max\Big(dp[u][used + take + 1],\, dp[u][used] + dp[v][take] + w(u, v)\Big)

其中：

$used$ 为合并当前儿子之前，在节点 $u$ 的前面若干子树中已保留的边数；
$take$ 为在当前儿子 $v$ 的子树中保留的边数；
转移前先将旧状态拷贝至临时数组，保证每组只选一个选项，避免同组内重复累加。

3. 转移关系示意

graph G {
  U [label="u"];
  V [label="v"];
  X [label="v 子树里的保留边"];
  U -- V [label="w(u, v) (必留)"];
  V -- X;
}

若想要保留 $X$ 中的任意枝条，边 $U-V$ 必须保留，这正是转移中 $+1$ 条边与 $+w(u, v)$ 的来源。

转移演算: 样例树上逐组背包的过程

样例 5 2 的边为 $(1,3,1)$ 、 $(1,4,10)$ 、 $(2,3,20)$ 、 $(3,5,20)$ , 以 $1$ 为根后结构是

flowchart TB
  N1["1"] -->|"w=1"| N3["3"]
  N1 -->|"w=10"| N4["4 (叶子)"]
  N3 -->|"w=20"| N2["2 (叶子)"]
  N3 -->|"w=20"| N5["5 (叶子)"]

结点处理顺序(后序)为 $2,5,3,4,1$ . 下表按"合并到父结点的先后"列出每一步, 数组写的是 $dp[u][0..Q]$ , 其中 $Q = 2$ :

步骤	动作	数组变化
1	叶子 $2$ 初始化	$dp[2] = [0,0,0]$
2	叶子 $5$ 初始化	$dp[5] = [0,0,0]$
3	把 $2$ 并入 $3$ ( $w=20$ )	$dp[3] = [0,20,0]$
4	把 $5$ 并入 $3$ ( $w=20$ )	$dp[3] = [0,20,40]$
5	叶子 $4$ 初始化	$dp[4] = [0,0,0]$
6	把 $3$ 并入 $1$ ( $w=1$ )	$dp[1] = [0,1,21]$
7	把 $4$ 并入 $1$ ( $w=10$ )	$dp[1] = [0,10,21]$

第 3 步能看懂 $+1$ 的含义: 想留 $2$ 就必须同时留边 $1$ - $3$ 与 $3$ - $2$ , 所以 $dp[3][1] = 0 + dp[2][0] + 20 = 20$ . 第 4 步再并入 $5$ , 得到 $dp[3][2] = dp[3][1] + dp[5][0] + 20 = 40$ , 即两条 $20$ 权边都留下.

第 7 步是本题最容易被忽略的地方: $dp[1][1]$ 从 $1$ 变成 $10$ , 说明"只留一条边"时应该留权值更大的 $1$ - $4$ 而不是 $1$ - $3$ . 但最终答案取 $dp[1][Q] = dp[1][2] = 21$ , 它来自第 6 步保留下来的 $1$ - $3$ 加 $3$ - $2$ 组合( $1 + 20 = 21$ ), 与 $1$ - $4$ 无关. 这就是分组背包"每个儿子是一组、组内只能选一个 $take$ "的作用: 第 7 步只可能改善 $dp[1][1]$ , 不会覆盖掉 $Q=2$ 时的更优解.

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

struct Edge {
    int to;
    int w;
};

int n, q_need;
vector<Edge> g[MAXN];
int parent_arr[MAXN];
int parent_w[MAXN];
int sub_edge_cnt[MAXN];
int dp[MAXN][MAXN];

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

    cin >> n >> q_need;
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        parent_arr[i] = 0;
        parent_w[i] = 0;
        sub_edge_cnt[i] = 0;
        for (int j = 0; j <= q_need; j++) {
            dp[i][j] = 0;
        }
    }

    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    vector<int> order;
    order.reserve(n);
    stack<int> st;
    st.push(1);
    parent_arr[1] = 0;

    while (!st.empty()) {
        int u = st.top();
        st.pop();
        order.push_back(u);
        for (size_t i = 0; i < g[u].size(); i++) {
            int v = g[u][i].to;
            if (v == parent_arr[u]) {
                continue;
            }
            parent_arr[v] = u;
            parent_w[v] = g[u][i].w;
            st.push(v);
        }
    }

    for (int idx = (int)order.size() - 1; idx >= 0; idx--) {
        int u = order[idx];
        sub_edge_cnt[u] = 0;

        for (size_t i = 0; i < g[u].size(); i++) {
            int v = g[u][i].to;
            int w = g[u][i].w;
            if (v == parent_arr[u]) {
                continue;
            }

            static int new_dp[MAXN];
            for (int t = 0; t <= q_need; t++) {
                new_dp[t] = dp[u][t];
            }

            for (int used = 0; used <= min(q_need, sub_edge_cnt[u]); used++) {
                for (int take = 0; take <= min(q_need - used - 1, sub_edge_cnt[v]); take++) {
                    // 若要从儿子子树里保留 take 条边，就必须先保留 u-v 这条边。
                    new_dp[used + take + 1] = max(new_dp[used + take + 1],
                                                   dp[u][used] + dp[v][take] + w);
                }
            }

            sub_edge_cnt[u] += sub_edge_cnt[v] + 1;
            for (int t = 0; t <= q_need; t++) {
                dp[u][t] = new_dp[t];
            }
        }
    }

    cout << dp[1][q_need] << '\n';
    return 0;
}

复杂度

时间复杂度：合并子树大小时，两重循环的枚举上限分别为子树当前的边数。树上背包的枚举复杂度严格受限于树上节点对数，结合子树大小优化后总时间复杂度为 $O(N \cdot Q) \le O(N^2)$ （最坏无剪枝上界为 $O(N \cdot Q^2)$ ）。在 $N, Q \le 100$ 的约束下，计算量不超过 $10^5$ 次操作，耗时 $< 5\text{ ms}$ 。
空间复杂度：动态规划数组 $dp[N][Q]$ 的大小为 $O(N \cdot Q)$ ，邻接表与树遍历栈的空间为 $O(N)$ ，总空间复杂度为 $O(N \cdot Q)$ ，约占几十 KB 内存。

总结

本题的关键在于通过树的层次结构拆解连通性约束：

父边制约：子树内的保留边必须经由父边导通至根节点，因此选儿子子树的任何非空方案都必须捆绑购买父边；
分组背包转化：每个儿子的子树构成相互独立的候选组，组内按分配边数展开为互斥候选项，通过树的后序遍历自底向上逐层合并即可高效求解。

图示解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录