【题目大意】

有n门选修课，每一门课都有固定的学分$S_i$，每个学生可以选m门课。有些选修课有先修课，每一门课最多只有一门先修课，求能获得的最多学分。

【思路解析】

设f[x][t]表示在以x结点为根的子树中选t门课能获得的最大学分，x的子结点集合为son[x]，子结点个数为p，且对于x的第i个子结点son[i]，以其为根结点的子树中选课数量为$C_i$，则转移方程为：$$f[x][t]=max(\sum_{i=1}^{p}f[son[i]][c[i]])+s[i](满足\sum_{i=1}^{p}c[i]=t-1)$$这个方程其实是一个分组背包模型，有p组物品，每组物品有t-1个，其中第i组的第j个物品体积为j，价值为f[son[i]][j]，背包的容积为t-1。

【代码实现】

1 #include
      
        2 #define rg register 3 #define go(i,a,b) for(rg int i=a;i<=b;i++) 4 #define back(i,a,b) for(rg int i=a;i>=b;i--) 5 #define ll long long 6 #define mem(a,b) memset(a,b,sizeof(a)) 7 using namespace std; 8 const int N=302; 9 vector
       
         son[N];10 int f[N][N],n,m,s[N];11 void dp(int x){12     f[x][0]=0;13     int size=son[x].size();14     go(i,0,size-1){
    //循环子结点(物品)15         int y=son[x][i];16         dp(y);17         back(t,m,0) back(j,t,0)18 //倒叙循环当前选课总门数(当前背包体积)19 //循环更深子树上的选课门数(组内物品),此处使用倒序是为了正确处理组内体积为0的物品20             if(t-j>=0) f[x][t]=max(f[x][t],f[x][t-j]+f[y][j]);21     }22     if(x!=0)//x不为0时,选修x本身要占掉一门课,并获得相应学分23         back(t,m,1) f[x][t]=f[x][t-1]+s[x];24     return;25 }26 int main(){27     scanf("%d%d",&n,&m);28     go(i,1,n){29         int fa;30         scanf("%d%d",&fa,&s[i]);31         son[fa].push_back(i);32     }33     mem(f,0);34     dp(0);35     printf("%d\n",f[0][m]);36     return 0;37 }