题目大意
??有一棵以1号点为根的树，每个树上有一定的苹果，你可以在树上来回走k步，问最多拿多少种苹果。
解题思路
??每个点一共有三种状态，一种是经过这个点一共走x步到了某个点，一种是回到这个点，一种是没回到这个点。
??状态表示:
??dp[i][j][1]: 回到了i点，一共在i的子树中走了j步最多拿多少苹果。对于这种状态，不管是先从u下到v的子树再回到u，然后去到u的其他子树中回去，还是u先下到其他子树中再回到u再下到v的子树再回到u都是一样的，本质上是一种状态。所以状态转移方程就是: dp[u][i+j+2][1] = max(dp[u][i+j+2][1], dp[u][i][1]+dp[v][j][1])
??dp[i][j][0]: 没有回到i点，一共在i的子树中走了j步最多拿多少苹果。对于这种状态，由于最后没有回到u，就有两种情况，一种是最终停到了u的其他子树中，一种是停到了v的子树中。
??第一种，先下到u的子树中再回到u再下到v的子树中：dp[u][i+j+1][0] = max(dp[u][i+j+1][0], dp[u][i][1]+dp[v][j][0])
??第一种，先下到v的子树中再回到u再下到u的子树中：dp[u][i+j+2][0] = max(dp[u][i+j+2][0], dp[u][i][0]+dp[v][j][1])
const int maxn = 2e2+10;
int n, m, a[maxn], dp[maxn][maxn][2];
vector<int> e[maxn];
void dfs(int u, int p) {
for (int i = m; i>=0; --i) dp[u][i][0] = dp[u][i][1] = a[u];
for (int k = 0; k<e[u].size(); ++k) {
int v = e[u][k];
if (v==p) continue;
dfs(v, u);
for (int i = m; i>=0; --i)
for (int j = m-i; j>=0; --j) {
dp[u][i+j+1][0] = max(dp[u][i+j+1][0], dp[u][i][1]+dp[v][j][0]);
dp[u][i+j+2][0] = max(dp[u][i+j+2][0], dp[u][i][0]+dp[v][j][1]);
dp[u][i+j+2][1] = max(dp[u][i+j+2][1], dp[u][i][1]+dp[v][j][1]);
}
}
}
void init() {
clr(dp, 0);
for (int i = 1; i<=n; ++i) e[i].clear();
}
int main() {
IOS;
while(cin >> n >> m) {
init();
for (int i = 1; i<=n; ++i) cin >> a[i];
for (int i = 1; i<n; ++i) {
int a, b; cin >> a >> b;
e[a].push_back(b);
e[b].push_back(a);
}
dfs(1, -1);
cout << max(dp[1][m][0], dp[1][m][1]) << endl;
}
return 0;
}