原题链接
1 题目
1.1 题目所需求出内容
对于本题，最终要求：一个最大值
1.2 题目背景、允许、禁止与限制
背景：
有一个含 nnn 个节点的严格二叉树和一个整数 qqq，代表需要保留二叉树上的 qqq 条边
允许：
每条边 E=(u,v)E=(u,v)E=(u,v) 都有一个权值 www，代表 u→vu\rightarrow vu→v 有 www 个苹果
求保留 qqq 条边后最多可获得的苹果数量
限制：
整棵二叉树以节点 111 为根，选出的若干条边一定能和根节点 111 直接或间接相连
1.3 题目数据范围与猜测
1≤n≤100⟶O(n3)1 \le n \le 100 \longrightarrow O(n^3)1≤n≤100⟶O(n3)
1.4 一句话概括题意
有一棵严格二叉树，求在满足条件的情况下保留 qqq 条边得到的最大苹果数量
2 题目破题推导
2.1 大拆小，小组大
当以 uuu 为根的子树中已经选了 aaa 条边，那么留给 uuu 的所有子节点 vvv 的留边数量 b=q−a−1b=q-a-1b=q−a−1
解释：qqq：一共可选 qqq 条边，aaa：已经选择了 aaa 条边，111：为了能让 vvv 这个子树选若干边，需要使 u→vu\rightarrow vu→v 这条边也被选上
那一共能获得的价值呢？是“以 uuu 为根的子树中已经选了 aaa 条边的价值”加上“以 vvv 为根的子树中已经选了 bbb 条边的价值”再加上“u→vu\rightarrow vu→v 的价值”
3 模型匹配
> 格式为："关键词：...... ⟶\longrightarrow⟶ ......\huge{......}......"
关键词：树形结构，动态求取最小值 ⟶\longrightarrow⟶ 树形dp（背包问题）\huge{树形dp（背包问题）}树形dp（背包问题）
注意这题为了不重复选子树，可以理解成是 0/1背包问题\huge{0/1背包问题}0/1背包问题
4 最终代码（禁止抄袭，仅用于参考）
