style="color:darkblue">【题目描述】margin-right:auto;
style="background-color:#fcfcfc">style="color:#000000">有一棵二叉苹果树，如果数字有分叉，一定是分两叉，即没有只有一个儿子的节点。
这棵树共
个节点，标号
style="background-color:#fcfcfc">style="color:#000000">我们用一根树枝两端连接的节点编号描述一根树枝的位置。
一棵有四根树枝的苹果树，因为树枝太多了，需要剪枝。
但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。
/>
style="color:darkblue">【输入】margin-right:auto;
style="background-color:#fcfcfc">，N
表示要保留的树枝数量。
style="background-color:#fcfcfc">N−1
行描述树枝信息，每行三个整数，前两个是它连接的节点的编号，第三个数是这根树枝上苹果数量。
style="color:darkblue">【输出】margin-right:auto;
style="background-color:#fcfcfc">style="color:#000000">输出仅一行，表示最多能留住的苹果的数量。
style="color:darkblue">【输入样例】style="background-color:#f1f1f1">5
20style="color:darkblue">【输出样例】style="background-color:#f1f1f1">21style="color:darkblue">【提示】margin-right:auto;
style="background-color:#fcfcfc">style="color:#000000">数据范围与提示：
style="background-color:#fcfcfc">100%
的数据，1≤Q≤N≤100,N≠1，每根树枝上苹果不超过
30000
个。
在树形动态规划中，“树上背包”是一类非常经典的问题。
它的特点是：我们需要在树形结构中选取若干节点或边，在满足“依赖关系”（选子节点必须选父节点）和“容量限制”（总数不超过Q）的前提下，使得总价值最大。
今天我们以经典题目二叉苹果树为例，深入剖析如何从零构建树形背包的状态转移方程，并掌握
O(NM)
题目重述
题目描述：
有一棵N个节点的二叉树（根节点为
1），树枝上长有苹果。
现在需要剪掉多余的树枝，只保留
Q根树枝。
求在满足保留树枝数量不超过Q的前提下，能留住的最大苹果数量。
关键约束：
依赖性：如果想要保留子树中的树枝，必须先保留连接该子树的父节点树枝。
容量限制：树枝总数<=Q。
/>2.
算法核心：分组背包模型
这道题本质上是“分组背包”在树上的应用。
对于当前节点u，它的每一个子节点v及其子树，都可以看作是一个“物品组”。
状态定义
状态转移方程
对于节点u和它的一个子节点v（连接边的苹果数为w）：
如果我们决定在v的子树里投入资源，那么：
必须先消耗1根树枝用来连接/>。
假设我们在v内部再分配k根树枝。
那么总消耗为k+1。
转移方程如下：
dp[u][j]
=/>
其中：
j倒序遍历（类似
0/1
背包，防止重复利用同一个子树）。
k遍历子树可能的树枝分配数。
/>3.
双向存边与数组大小
题目输入不保证父子顺序，因此必须建立无向图（双向addedge）。
2.
父节点判断
(防止死循环)
在DFS遍历邻接表时，由于是无向图，必须判断if(v==fa)。
3.
Size优化
(时间复杂度关键)
这是树形背包最核心的优化。
如果不加优化，三层循环的复杂度接近O(/>)。
加上sz数组记录子树大小后：
j的上限取min(q,sz[x]-1)。
k的上限取min(j,sz[v])-1。
这使得算法实际上只合并了每一对点一次，均摊复杂度降为/>4.
//dp[i][j]代表当前是第i个节点的团队在可以保留j个数枝的情况下最大保留苹果数
int
while(p!=-1){//遍历当前根节点的所有儿子
int
//因为我之前是存的双边，这一步目的是找到正确父子关系
if(v==fa)
sz[x]+=sz[v];//子树的节点也要加入x团队
//分组背包，每个子树是一组物品，然后因为优化了一维（当前是哪颗子树）
//数枝数量背包容量最多取到min(q,sz[x]-1)，最少有0根树枝
for(int
j=min(q,sz[x]-1);j>=0;j--){
//分配给当前这个子树多少容量（数枝数量）
//k不能取到j，因为x连接子树根节点v就需要一颗树枝，所以子树最多得到j-1根树枝
//同时子树有sz[v]个节点，那最多能有sz[v]-1根树枝
for(int
k=0;k<min(j,sz[v]);k++){
//这里要写dp[x][j-k-1]而不能写dp[x][j-k]
//因为连接子树也需要一根树枝
dp[x][j]=max(dp[x][j],dp[x][j-k-1]+dp[v][k]+wt[p]);
p=nxt[p];
cin>>u>>v>>w;
addedge(u,v,w);
dfs(1,0);//题目给出树根编号一定是1,根节点没有父节点
return
总结
循环边界：
初始化：
sz[x]初始为
1（节点数）。
dp数组全局初始化为
0，符合题目逻辑（不保留树枝则价值为
0）。
复杂度：
