动态规划之【树形DP】第2课：树形DP应用案例实践1
动态规划之【树形DP】第2课：树形DP应用案例实践1
二叉苹果树
题目描述
有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点）
这棵树共有N NN个结点（叶子点或者树枝分叉点），编号为1 ∼ N 1 \sim N1∼N，树根编号一定是1 11。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4 44个树枝的树：
2 5 \ / 3 4 \ / 1现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量，求出最多能留住多少苹果。
留住一个苹果的定义为苹果所在枝条直接与根相连或通过其他枝条间接与根相连。
输入格式
第一行2 22个整数N NN和Q QQ，分别表示表示树的结点数，和要保留的树枝数量。
接下来N − 1 N-1N−1行，每行3 33个整数，描述一根树枝的信息：前2 22个数是它连接的结点的编号，第3 33个数是这根树枝上苹果的数量。
输出格式
一个数，最多能留住的苹果的数量。
输入输出样例 #1
输入 #1
5 2 1 3 1 1 4 10 2 3 20 3 5 20输出 #1
21说明/提示
1 ⩽ Q < N ⩽ 100 1 \leqslant Q < N \leqslant 1001⩽Q<N⩽100，每根树枝上的苹果⩽ 3 × 10 4 \leqslant 3 \times 10^4⩽3×104。
思路分析
题目描述：给定一棵二叉树，每条树枝上有若干苹果。要求保留m条树枝（即边），使得剩下的苹果总数最大。剪枝规则是：若剪掉某条树枝，则其子树上的所有树枝都会被剪掉。
题目分析：
- 留q个树枝，转换为留q+1个结点
- 把树枝上的苹果数，转换到结点上
- 对于树中的每棵子树，要保留j个结点 （因为根必须保留，所以需要保留j-1个子结点），如果左子树保留k个结点，则右子树需保留j-1-k个结点
状态定义：
dp[i][j]表示以节点i为根的子树保留j个结点时的最大苹果数。
状态转移方程：
dp[i][j]=max(dp[i][j],dp[L[i]][k]+dp[R[i]][j-1-k]+a[i])其中：0≤k≤j-1， L[i]表示i结点的左儿子， R[i]表示i结点的右儿子 边界条件： j==0时，dp[i][0]=0//保留0个结点j!=0&&L[i]==0&&R[i]==0时，dp[i][j]=a[i]//叶子结点最终求解的答案为： dp[1][q+1]实现步骤
1.核心逻辑：
- 问题转化：将边权值转化为子节点的权值，保留子节点即意味着保留其父边。
- 树形DP：通过递归分治，将问题分解为左右子树的子问题，利用记忆化避免重复计算。
2.数据结构与初始化：
- 使用邻接矩阵
a存储树的边及其权值（苹果数）。 L和R数组分别记录每个节点的左、右子节点。w数组存储每个节点到其父节点的边权值。dp[i][j]为动态规划数组，表示以节点i为根的子树保留j个节点时的最大苹果数。
3.建树过程（DFS）：
- 通过深度优先搜索遍历树，将每个节点的子节点转换为二叉树结构，记录左、右子节点，并存储对应边的权值到
w数组中。
4.动态规划（记忆化搜索）：
- 函数
f(i, j)递归计算以i为根的子树保留j个节点的最大苹果数。 - 状态转移：枚举左子树保留
k个节点，右子树保留j-1-k个节点（当前节点占1个），取左右子树最大值之和加上当前节点的权值（w[i]）。 - 边界条件：叶子节点直接返回其权值，保留0个节点返回0。
5.输入输出处理：
- 输入边信息构建邻接矩阵，并转换为二叉树结构。
- 最终输出
f(1, q+1)，因为保留q条边对应保留q+1个节点，确保根节点必须保留。
代码实现
#include<bits/stdc++.h>usingnamespacestd;intn,q,x,y,z;intL[110],R[110];//存结点的左右儿子inta[110][110];//邻接矩阵intdp[110][110];//dp[i][j]:表示以节点 i为根的子树保留 j个结点时的最大苹果数intw[110];//结点的苹果数//建树voiddfs(intx,intfa){//x是结点编号，fa是x的父结点编号for(inti=1;i<=n;i++){if(a[x][i]!=-1&&i!=fa){if(L[x]==0){L[x]=i;//i是x的左孩子w[i]=a[x][i];//i结点的苹果数}elseif(R[x]==0){R[x]=i;//i是x的右孩子w[i]=a[x][i];//i结点的苹果数}dfs(i,x);}}}//i结点为根的子树，保留j个结点的最大苹果树intf(inti,intj){if(j==0)return0;//保留0个结点if(L[i]==0&&R[i]==0)returnw[i];//叶子结点if(dp[i][j]!=-1)returndp[i][j];//记忆化递归for(intk=0;k<=j-1;k++){dp[i][j]=max(dp[i][j],f(L[i],k)+f(R[i],j-1-k)+w[i]);}returndp[i][j];}intmain(){cin>>n>>q;memset(a,-1,sizeof(a));//a数组初始化memset(dp,-1,sizeof(dp));//dp数组初始化for(inti=1;i<=n-1;i++){cin>>x>>y>>z;a[x][y]=z;//无向图a[y][x]=z;}//建树dfs(1,0);//1是根结点，0表示根结点没有父亲//输出答案cout<<f(1,q+1);return0;}完整系列资料，请查看专栏：《csp信奥赛C++动态规划》
https://blog.csdn.net/weixin_66461496/category_13096895.html
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}【秘籍汇总】（完整csp信奥赛C++学习资料）：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
https://edu.csdn.net/course/detail/41081 点击跳转
3、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转
4、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转
5、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}