又是一道树状dp题目，感觉好难，看的网上的解析才做出来，不过比第一次遇到这种题目时要好多了，加油，多遇到几次就会了。

 

 

 

代码：

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int MAX = 105;int dp[MAX][MAX];int bug[MAX], brain[MAX];int n, m;int vis[MAX]; vector
        
          tree[MAX];        //图 void dfs(int root);int main(){//    freopen("input.txt", "r", stdin);        while(cin >> n >> m && n != -1){        for(int i=1; i<=n; i++){            cin >> bug[i] >> brain[i];            bug[i] = (bug[i] + 19) / 20;    //转化为需要消耗多少战士，向上取整            tree[i].clear();         }        for(int i=1; i
         
          > u >> v;            tree[u].push_back(v);            tree[v].push_back(u);        }                if(m == 0){            cout << 0 << endl;    continue;        }                memset(vis, 0, sizeof(vis));        memset(dp, 0, sizeof(dp));        dfs(1);                cout << dp[1][m] << endl;    }        return 0;} void dfs(int root){    vis[root] = 1;        if(m < bug[root])        return;        for(int i=bug[root]; i<=m; i++){        dp[root][i] = brain[root];        //当军队数大于等于bug[root],则至少可以获取到 brain [root] 的大脑     }        for(int i=0; i
          
           =bug[root]; j--){ //背包容量为 j 时 for(int k=j-1; k>=bug[root]; k--){ //root 这颗树 k 个战士 //如果放第 i 棵子树，则脑量等于包括root和前面 i-1 棵子树 k 个战士获取的最大脑量加上第 i 棵子树能获取的最大脑量 dp[root][j] = max(dp[root][j], dp[root][k] + dp[v][j-k]); } } }}