二叉苹果树

GitHub跳转原题关系图返回列表

设 dp[u][j] 为在 u 子树中保留 j 条且仍能通过 u 连到根的边的最优收益，合并儿子时做树上分组背包。

OJ: luogu

题目 ID: P2015

难度:普及+/提高

标签:树形DP树上背包动态规划树

日期: 2026-06-21 03:50

目录

  1. 题意
  2. 思路
    1. DP 转移方程
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

给一棵树，每条边上有若干苹果。

现在恰好保留 Q 条边，要求保留下来的这些边仍然和根 1 连通，并使留下的苹果数最大。

思路

先看一个可以直接验证想法的朴素解：

cpp
#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;
}

brute.cpp 把每条边看成一个 01 选择：chosen[i] = 0/1 表示不保留或保留。递归先生成完整选择，叶子节点再检查是否恰好保留 Q 条边、这些边是否都能和根连通，并统计苹果数。 这个做法完全正确，但显然不能作为正解。

这题是很标准的树上背包。

设 dp[u][j] 表示：

  • 在 u 子树里
  • 恰好保留 j 条边
  • 且这些边都能通过 u 连回根

时能得到的最大苹果数。

为什么这个状态定义很自然？

因为如果想从儿子 v 子树里保留任何边，那么父边 u-v 本身也必须保留，否则这些边就断掉了，不能算留下。

所以合并儿子时，如果从 v 子树中拿 take 条边，那么：

  • 边数会增加 take + 1
  • 收益会增加 dp[v][take] + w(u,v)

于是整个过程就是一个树上的分组背包。

DP 转移方程

合并儿子 v 时，若当前 u 已经保留 used 条边，从 v 子树保留 take 条边，则：

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

这里的 +1 就是必须额外保留父边 u-v。

下面这张图可以帮助理解“为什么父边也必须保留”：

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

如果你想让 X 这部分苹果还能连到根，那么 U-V 这条边一定不能剪掉。 这正是转移里 +1 的来源。

代码

cpp
#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;
}

复杂度

本题 N <= 100，树上背包总复杂度是 O(N3)O(N^3)，空间复杂度是 O(N2)O(N^2)。

总结

这题最关键的理解就是：

  • 儿子子树里的边如果想保留下来，父边也必须一起保留

看清这一点后，状态设计和转移都会非常自然。

一图流解析

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

一图流解析