解题思路：树形动态规划（Tree DP）

1. 问题分析

题目要求在一棵苹果树（无向无环图）上，从根节点1出发，在最多移动K步的情况下，计算能够采摘的最大苹果数量。关键在于：

• 每移动一步消耗1步数
• 可以自由选择路径，但步数有限
• 需要遍历可能路径，找出最优解

2. 算法选择

采用树形动态规划，原因：

• 树结构适合递归处理
• 需要记录不同步数下的最优解
• 状态转移需要考虑是否返回当前节点

3. 状态设计

定义三维DP数组：

• dp[u][j][0]：在节点u的子树中，消耗j步且不回到u节点能获得的最大苹果数
• dp[u][j][1]：在节点u的子树中，消耗j步且回到u节点能获得的最大苹果数

4. 核心逻辑

1. 初始化：

   • 每个节点初始化为自己的苹果数
   • 邻接表建树

2. DFS遍历：

   • 后序遍历处理子树
   • 对每个子节点，更新当前节点的DP状态

3. 状态转移：

   // 不回到root的情况
   dp[root][j][0] = max(不进入该子树, 进入该子树且不返回)
   
   // 回到root的情况 
   dp[root][j][1] = max(不进入该子树, 进入该子树且返回)
   

   具体实现：

   • 消耗jj步进入子树son
   • 剩余j-jj步用于其他子树
   • 根据是否返回进行不同计算

5. 关键代码解析

for(int j = k; j >= 1; j--) {
    for(int jj = 1; jj <= j; jj++) {
        // 情况1：不回到root
        dp[root][j][0] = max(dp[root][j][0], 
                           dp[root][j-jj][0] + dp[son][jj-2][0]);
        
        // 情况2：回到root（两种子情况）
        dp[root][j][1] = max(dp[root][j][1],
                           dp[root][j-jj][0] + dp[son][jj-1][1]);
        dp[root][j][1] = max(dp[root][j][1],
                           dp[root][j-jj][1] + dp[son][jj-2][0]);
    }
}

6. 复杂度分析

• 时间复杂度：O(N*K²)
  • 每个节点处理K²次状态转移
  • N个节点共O(N*K²)
• 空间复杂度：O(N*K)
  • 主要消耗在DP数组

7. 示例推演

以样例输入1为例：

2 1
0 11
1 2

• 从节点1出发，1步可以到节点2
• dp[1][1][0] = 11（不返回）
• 最终取max(0,11)=11

8. 算法优势

1. 准确处理树形结构
2. 通过状态设计区分是否返回
3. 逆向更新避免重复计算
4. 完美适配题目约束条件

9. 注意事项

• 步数计算要准确（进入子树消耗jj-1或jj-2步）
• 初始化时每个节点自带苹果
• 邻接表需要双向建边

标程

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> v[105];
int dp[105][205][2], val[105];
int n, k;

void dfs(int root, int father) {
	int len = v[root].size();
	for (int i = 0; i < len; i++) {
		int son = v[root][i];
		if (son == father)
			continue;
		dfs(son, root);
		for (int j = k; j >= 1; j--) {
			for (int jj = 1; jj <= j; jj++) {
				dp[root][j][0] = max(dp[root][j][0], dp[root][j-jj][0] + dp[son][jj-2][0]);
				dp[root][j][1] = max(dp[root][j][1], dp[root][j-jj][0] + dp[son][jj-1][1]);
				dp[root][j][1] = max(dp[root][j][1], dp[root][j-jj][1] + dp[son][jj-2][0]);
			}
		}
	}
}

int main() {
	while (scanf("%d%d", &n, &k) == 2) {
		for (int i = 0; i <= n; i++)
			v[i].clear();
		memset(dp, 0, sizeof(dp));
		for (int i = 1; i <= n; i++) {
			scanf("%d", &val[i]);
			for (int j = 0; j <= k; j++)
				dp[i][j][0] = dp[i][j][1] = val[i];
		}
		int a, b;
		for (int i = 1; i < n; i++) {
			scanf("%d%d", &a, &b);
			v[a].push_back(b);
			v[b].push_back(a);
		}
		dfs(1, 0);
		printf("%d\n", max(dp[1][k][0], dp[1][k][1]));
	}
	return 0;
}