树上背包问题的典例，记下来

---

solution

设\(dp[x][t]\)表示以\(x\)为子树，选\(t\)门课获得的最大学分

设\(p\)是\(x\)的子节点数量，\(c_i\)是\(x\)的子节点\(y_i\)选修的课数

转移方程如下

\[dp[x][t]=max_{\sum_{i=1}^pc_i=t-1}\{\sum_{i=1}^pdp[y_i][c_i]\}+pnt[x]\]

事实上，这是一个分组背包模型，对于每个节点\(x\)，每个子节点\(y_i\)是一个组，在其中选取不超过\(1\)个元素\(c_i\)加入背包。将当前枚举到的组作为阶段

对于没有先修课的课程，我们可以将一个超级根节点\(0\)作为它们的父节点，方便计算

Code

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define maxn 305#define maxm 305using namespace std;typedef long long ll;int n,m;vector
           
             son[maxn];int prt[maxn];int pnt[maxn];int dp[maxn][maxm];void DP(int u){ for(register int i=0;i
            
             =0;--t)//枚举背包已经放入的体积 for(register int j=t;j>=0;--j) dp[u][t]=max(dp[u][t],dp[u][t-j]+dp[v][j]); } if(u!=0)//除超级根节点外，每个节点的选取都会获得pnt[u]的学分 for(register int t=m;t>0;--t) dp[u][t]=dp[u][t-1]+pnt[u];}int main(){ scanf("%d%d",&n,&m); int k; for(register int i=1;i<=n;++i) { scanf("%d%d",&k,&pnt[i]); prt[i]=k; } for(register int i=1;i<=n;++i) son[prt[i]].push_back(i); DP(0); printf("%d",dp[0][m]); return 0;}