题意：某个课只有它父节点选的时候他才能选，问n个点构成的树，选m个课的最大学分数。 思路：构建一个虚拟节点0，那么0就是必选了，把选的课数量+1，对问题造成的影响是等价的，然后就是熟悉的分组背包问题了，早上卡了很久，因为要空出一格来放父亲的节点，然后对于背包dp的顺序是不能改变的，1物品组2体积最后是决策，里面只能选m-1个点，因为要留一个给自己放。 ac代码：
#include<bits/stdc++.h> using namespace std; const int N=310; int f[N][N]; int w[N]; int e[N*2],ne[N*2],h[N],idx; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int n; int m; void dfs(int u) { for(int i=h[u];~i;i=ne[i]) { int j=e[i]; // cout<<j<<endl; dfs(j); for(int k=m-1;k>=1;k--) for(int jj=0;jj<=k;jj++) f[u][k]=max(f[u][k],f[u][k-jj]+f[j][jj]); } for(int k=m;k>=1;k--) f[u][k]=f[u][k-1]+w[u]; } int main() { memset(h,-1,sizeof h); cin >> n >> m; for(int i=1;i<=n;i++) { int x; cin>>x>>w[i]; add(x,i); } m++; dfs(0); //cout<<f[3][1]<<endl; cout<<f[0][m]<<endl; }