设d(u, j, 0)表示在以u为根的子树中至多走k步并且最终返回u，能吃到的最多的苹果。
则有状态转移方程：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 using namespace std; 7 8 const int maxn = 100 + 10; 9 const int maxk = 200 + 10; 10 int n, k; 11 12 int a[maxn]; 13 int d[maxn][maxk][2]; 14 vector<int> G[maxn]; 15 16 void dfs(int u, int fa) 17 { 18 for(int i = 0; i < G[u].size(); i++) 19 { 20 int v = G[u][i]; 21 if(v == fa) continue; 22 dfs(v, u); 23 for(int j = k; j >= 1; j--) 24 for(int t = 1; t <= j; t++) 25 { 26 if(t > 1) d[u][j][0] = max(d[u][j][0], d[u][j-t][0] + d[v][t-2][0]); 27 if(t > 1) d[u][j][1] = max(d[u][j][1], d[u][j-t][1] + d[v][t-2][0]); 28 d[u][j][1] = max(d[u][j][1], d[u][j-t][0] + d[v][t-1][1]); 29 } 30 } 31 } 32 33 int main() 34 { 35 while(scanf("%d%d", &n, &k) == 2 && n) 36 { 37 for(int i = 1; i <= n; i++) G[i].clear(); 38 memset(d, 0, sizeof(d)); 39 for(int i = 1; i <= n; i++) 40 { 41 scanf("%d", a + i); 42 for(int j = 0; j <= k; j++) d[i][j][0] = d[i][j][1] = a[i]; 43 } 44 for(int i = 1; i < n; i++) 45 { 46 int u, v; scanf("%d%d", &u, &v); 47 G[u].push_back(v); G[v].push_back(u); 48 } 49 50 dfs(1, 0); 51 52 printf("%d ", max(d[1][k][0], d[1][k][1])); 53 } 54 55 return 0; 56 }