```cpp
void dfs(int x,int fa)
{
for(int i=head[x];i;i=tree[i].next)
{
if(tree[i].to!=fa)
{
dp[tree[i].to][1]=tree[i].w;
dfs(tree[i].to,x);
for(int j=q;j>0;--j)
{
for(int k=0;k<=j;++k)
{
if((j!=1&&k!=j)||x==1)
{
dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[tree[i].to][k]);
}
}
}
}
}
return ;
}
```
by 马桶战神 @ 2021-08-20 22:13:45
树形dp最好往记忆化递归想，其实记忆化递归本质上就是dp，记忆化递归最关键的也是找状态方程和设置状态数组，这题dp[i][j]定义为第i个节点当前剩下k个边可取的情况下的最大苹果值
由于相当于度为2的树，那么其实就是左子树从k取到0加上右子树从0取到k
dp[i][k] = (k = q-0)max(dp[2i+1][k]+dp[2i+2][q-k])
by WhyCodePo @ 2022-04-11 19:28:46