传送门
这道题是个很好做的二叉树
首先考虑给DP数组下定义，一般来说树形DP的DP数组的第一维都是当前节点的编号。
这道题光一维肯定是不够的 ，那么加维，发现dp[i][j]表示当前节点为i，保留j个节点的最大苹果数量比较ok。 那么方程就显而易见了，dp[i][j]=max(dp[i][j],dp[i.lson][k]+dp[i.rson][j-k-1]+apple[i])。 另外，还可以在dfs时运用记忆化，可以大大提高速度 。 再提一句，由于题目中给的权值在边上，让人特别难受，于是，我们把权值转化到儿子上会方便操作。
#include<bits/stdc++.h> using namespace std; const int N=150; int n,q,dp[N][N]; struct node { int lson; int rson; int val; }tree[N*20]; int dfs(int now,int point) { if(now==0||point==0) { return 0; } if(tree[now].lson==0&&tree[now].rson==0) { return tree[now].val; } if(dp[now][point]>0) return dp[now][point];//记忆化 for(int k=0;k<point;k++) //枚举方程中的k { dp[now][point]=max(dp[now][point],dfs(tree[now].lson,k)+dfs(tree[now].rson,point-k-1)+tree[now].val); } return dp[now][point]; } int main() { cin>>n>>q; for(int i=1;i<=n-1;i++) { int fa,son,v; cin>>fa>>son>>v; tree[son].val=v; if(tree[fa].lson==0) tree[fa].lson=son; else tree[fa].rson=son; } cout<<dfs(1,q+1);//注意是q+1 因为把边变成了点 return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9391548.html
相关资源：各显卡算力对照表！