洛谷 P2015 分析（别看）

科技起源‍‍‍‍‍‍‍‍‍‍‍‍

2026-07-21 13:08:15

发布于：北京

7阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最大值

1.2 题目背景、允许、禁止与限制

背景：
有一个含 $n$ 个节点的严格二叉树和一个整数 $q$ ，代表需要保留二叉树上的 $q$ 条边
允许：
每条边 $E=(u,v)$ 都有一个权值 $w$ ，代表 $u\rightarrow v$ 有 $w$ 个苹果
求保留 $q$ 条边后最多可获得的苹果数量
限制：
整棵二叉树以节点 $1$ 为根，选出的若干条边一定能和根节点 $1$ 直接或间接相连

1.3 题目数据范围与猜测

$1 \le n \le 100 \longrightarrow O(n^3)$

1.4 一句话概括题意

有一棵严格二叉树，求在满足条件的情况下保留 $q$ 条边得到的最大苹果数量

2 题目破题推导

2.1 大拆小，小组大

当以 $u$ 为根的子树中已经选了 $a$ 条边，那么留给 $u$ 的所有子节点 $v$ 的留边数量 $b=q-a-1$
解释： $q$ ：一共可选 $q$ 条边， $a$ ：已经选择了 $a$ 条边， $1$ ：为了能让 $v$ 这个子树选若干边，需要使 $u\rightarrow v$ 这条边也被选上
那一共能获得的价值呢？是“以 $u$ 为根的子树中已经选了 $a$ 条边的价值”加上“以 $v$ 为根的子树中已经选了 $b$ 条边的价值”再加上“ $u\rightarrow v$ 的价值”

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：树形结构，动态求取最小值 $\longrightarrow$ $\huge{树形dp（背包问题）}$
注意这题为了不重复选子树，可以理解成是 $\huge{0/1背包问题}$

4 最终代码（禁止抄袭，仅用于参考）

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

int n, q;
const int N = 111;
struct node{
    int to;
    int w;
};
vector<node> g[N];
int dp[N][N];
const int INF = 0x3f3f3f3f3f3f3f3f;
void dfs(int u, int fa){
    dp[u][0] = 0;
    for (node now : g[u]){
        int v = now.to;
        int w = now.w;
        if (v == fa){
            continue;
        }
        dfs(v, u);
        for (int a = q;a >= 0;a--){
            if (dp[u][a] == -INF){
                continue;
            }
            for (int b = 0;b <= q - a - 1;b++){
                if (dp[v][b] == -INF){
                    continue;
                }
                dp[u][a + b + 1] = max(dp[u][a + b + 1], dp[u][a] + dp[v][b] + w);
            }
        }
    }
}

signed main(){

    cin >> n >> q;
    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});
    }
    memset(dp, -0x3f, sizeof(dp));
    dfs(1, -1);
    cout << dp[1][q];
    
    return 0;
}