其实就是把背包dp搬树上了，
注意每一个节点必须要先选自己才能选孩子节点
#include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<cstring> using namespace std; const int inf=0x3f3f3f3f; int n,m,val[305],f[305][305];//第i个节点选j个课程 bool b[305]; int tot,head[305],to[305],pre[305]; void addedge(int x,int y) { to[++tot]=y;pre[tot]=head[x];head[x]=tot; } void dfs(int u) { f[u][1]=val[u];//因为必须要保证先选根节点再选叶子节点！！ for (int i=head[u];i;i=pre[i]) { int v=to[i]; dfs(v); for (int j=m;j>=1;j--)//枚举的时候也不能出现不选根节点的情况 ，也就是说不能从0号开始枚举，其实这里j枚举的u节点现在选了几个点，l枚举v这个子节点选几个点，注意不能超了 { for (int l=1;l<m;l++) if (j+l<=m) f[u][j+l]=max(f[u][j+l],f[u][j]+f[v][l]); else break; } } } int main() { scanf("%d%d",&n,&m);m++;//因为0号节点，需要选 int u; for (int i=1;i<=n;i++) { scanf("%d%d",&u,&val[i]); addedge(u,i); } memset(f,-inf,sizeof(f)); dfs(0); printf("%d",f[0][m]); return 0; }