P2015 二叉苹果树
状态表示：
\(dp[u][j]\)：表示以结点u为根的子树上留j条边时的最多苹果数量。
状态转移：
状态转移方程如何设计？下面给出2种思路，二叉树方法、多叉树（一般性）方法。
（1）二叉树
本题是一棵二叉树，根据二叉树的特征，考虑u的左右子树，如果左子树\(l\)共留\(k\)条边（不包含\(u \rightarrow l\)这条边），右子树\(r\)则留\(j - k - 2\)条边（同样不包含\(u \rightarrow r\)这条边），减\(2\)的原因是除去\(u \rightarrow l\)以及\(u \rightarrow r\)，用\(k\)在\([0, j-2]\)内遍历不同的分割。
转移方程如下：
其中，\(f(l,j-1)\)表示\(j\)条边全部保留在左子树，\(f(r,j-1)\)表示\(j\)条边全部保留在右子树。\(f(l,k)\)和\(f(r,j-2-k)\)表示左子树保留\(k\)条边，右子树保留\(j-k-2\)条边。
边界：
\(f(leaf,j)=0\)，\(f(u,0)=0\)。
注意点
首先需要建树，原题输入数据并没有明确给出父子关系。建树后可将边权转化为儿子节点的点权。
const int N=110;
PII tree[N];
vector g[N];
int f[N][N];
int apple[N];
int n,m;
void build(int u,int fa)
{
for(int i=0;i>n>>m;
for(int i=0;i>a>>b>>c;
g[a].pb({b,c});
g[b].pb({a,c});
}
build(1,-1);
cout< （2）多叉树
状态转移：
\(v\)是\(u\)的一个子结点。\(dp[u][j]\)的计算分为2部分：
- \(dp[v][k]\)：在\(v\)上留\(k\)个边；
- \(dp[u][j-k-1]\)：除了\(v\)上的\(k\)个边，以及边\([u,v]\)，那么以\(u\)为根的这棵树上还有\(j-k-1\)个边，它们在u的其他子结点上。
const int N=110;
vector g[N];
int f[N][N];
int apple[N];
int n,m;
void dfs(int u,int fa)
{
for(int i=0;i=1;j--)
for(int k=0;k>n>>m;
for(int i=0;i>a>>b>>c;
g[a].pb({b,c});
g[b].pb({a,c});
}
dfs(1,-1);
cout< 有一些树形DP问题，可以抽象为背包问题，被称为“树形依赖的背包问题”。例如上面的题目“二叉苹果树”，可以建模为“分组背包”（注意与普通分组背包的区别是，这里的每个组可以选多个物品，而不是一个）：
（1）分组。根结点u的每个子树是一个分组。
（2）背包的容量。把u为根的整棵树上的树枝数，看成背包容量。
（3）物品。把每个树枝看成一个物品，体积为1，树枝上的苹果数量看成物品的价值。
（4）背包目标。求能放到背包的物品的总价值最大，就是求留下树枝的苹果数最多。
分组背包的代码和“二叉苹果树”的代码很像，下面贴出2个代码帮助理解。
（1）分组背包的代码。
for(int i = 1; i <= n; i++) //遍历每个组
for(int j = C; j>=0; j--) //背包总容量C
for(int k = 1; k <= m; k++) //用k遍历第i组的所有物品
if(j >= c[i][k]) //第k个物品能装进容量j的背包
dp[j] = max(dp[j], dp[j-c[i][k]] + w[i][k]); //第i组第k个
（2）树形dp代码。下面是洛谷P2015部分代码。
for(int i = 0; i < edge[u].size(); i++) { //把u的每个子树看成一个组
......
for(int j = m; j >= 1; j--) //把u的枝条总数看成背包容量
for(int k = 0; k < j ; k++) //用k遍历每个子树的每个枝条
dp[u][j] = max(dp[u][j], dp[u][j-k-1] + dp[v][k] + w);
树形背包问题的状态定义，一般用dp[u][j]表示以点u为根的子树中，选择j个点（或j个边）的最优情况。
原文：https://www.cnblogs.com/fxh0707/p/14640468.html