学步园

先描述一下状态；d[ 0 ][ root ][ j ]表示root节点不需回到root有j点能量可用最多能吃几个苹果；d[ 1 ][ root ][ j ]表示root节点必须需回到root有j点能量可用最多能吃几个苹果；

状态转移就很清晰了见代码；

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 105;
struct node{
  int to,val;
  node(int x=0,int y=0):to(x),val(y){}
}a[maxn];
int n,k,w[maxn],d[2][maxn][maxn*2],temp[2][maxn*2];
vector<int> G[maxn];
void solve(int root,int f){
  for(int i=0;i<=k;i++)
    d[0][root][i] = d[1][root][i] = w[root];

  for(int i=0;i<G[root].size();i++){
    int v = G[root][i];
    if(v==f) continue;
    solve(v,root);
    for(int i=0;i<=k;i++) {
        temp[0][i]=d[0][root][i];
        temp[1][i]=d[1][root][i];
    }
    for(int i=1;i<=k;i++)
      for(int j=1;j<=i;j++){
         d[0][root][i] = max(d[0][root][i],temp[1][i-j]+d[0][v][j-1]);
         if(j > 1){
         d[0][root][i] = max(d[0][root][i],temp[0][i-j]+d[1][v][j-2]);
         d[1][root][i] = max(d[1][root][i],temp[1][i-j]+d[1][v][j-2]);
         }
      }
  }
}
int main()
{
   while(scanf("%d %d",&n,&k)==2){
     for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
     }
     for(int i=1;i<=n;i++) G[i].clear();
     for(int i=1;i<n;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
     }
     solve(1,-1);
     printf("%d\n",d[0][1][k]);
   }
   return 0;
}