洛谷 P2015：二叉苹果树 ← 有依赖的背包问题

【题目来源】https://www.luogu.com.cn/problem/P2015【题目描述】有一棵苹果树如果树枝有分叉一定是分二叉就是说没有只有一个儿子的结点。这棵树共有 N 个结点叶子点或者树枝分叉点编号为 1∼N树根编号一定是 1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 4 个树枝的树2 5 \ / 3 4 \ / 1现在这颗树枝条太多了需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量求出最多能留住多少苹果。留住一个苹果的定义为苹果所在枝条直接与根相连或通过其他枝条间接与根相连。【输入格式】第一行 2 个整数 N 和 Q分别表示表示树的结点数和要保留的树枝数量。接下来 N−1 行每行 3 个整数描述一根树枝的信息前 2 个数是它连接的结点的编号第 3 个数是这根树枝上苹果的数量。【输出格式】一个数最多能留住的苹果的数量。【输入样例】5 21 3 11 4 102 3 203 5 20【输出样例】21【数据范围】1⩽QN⩽100每根树枝上的苹果 ⩽3×10^4。【算法分析】● 有依赖的背包树形背包核心是物品间存在选子必选父的单向依赖关系依赖结构通常为森林或多叉树主流解法为树形 DP 结合分组背包自底向上合并若题目中是双向强依赖、互相绑定的物品组选其一必全选则可先用并查集将连通块缩为超级物品再套用普通 01 背包求解两种思路对应不同依赖模型共同构成完整解法体系。● 有依赖的背包 / 树形背包 选儿子必须先选爹 把每个子树当成一组物品● 邻接表https://blog.csdn.net/hnjzsyjyj/article/details/155789364● 核心代码解析1f[u][k] 表示在以 u 为根的子树中保留 k 根树枝能得到的最大苹果数。2f[u][j]max(f[u][j],f[u][j-i-1]f[v][i]w) 中j-i-1 表示留给自己其他子树的树枝。-1 表示必须保留 u-v 这一条树枝。【算法代码】#include bits/stdc.h using namespace std; const int N105; vectorpairint,int g[N]; int f[N][N]; int n,V; void dfs(int u,int fa) { for(auto t:g[u]) { int vt.first; int wt.second; if(vfa) continue; dfs(v,u); for(int jV; j1; j--) { for(int i0; ij; i) { f[u][j]max(f[u][j],f[u][j-i-1]f[v][i]w); } } } } int main() { memset(f,0,sizeof f); cinnV; for(int i1; in; i) { int x,y,cnt; cinxycnt; g[x].push_back({y,cnt}); g[y].push_back({x,cnt}); } dfs(1,-1); coutf[1][V]endl; return 0; } /* in: 5 2 1 3 1 1 4 10 2 3 20 3 5 20 out: 21 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/159791882https://blog.csdn.net/hnjzsyjyj/article/details/159616887https://blog.csdn.net/hnjzsyjyj/article/details/159650172