本文共 2210 字，大约阅读时间需要 7 分钟。
本文出自
/**===================================================== * This is a solution for ACM/ICPC problem * * @source ：poj-2486 Apple Tree * @description : 树形背包dp * @author : shuangde * @blog : blog.csdn.net/shuangde800 * @email : zengshuangde@gmail.com * Copyright (C) 2013/08/23 22:17 All rights reserved. *======================================================*/ #include #include #include #include #include #include #include #define MP make_pair using namespace std; typedef pair PII; typedef long long int64; const int INF = 0x3f3f3f3f; const int MAXN = 110; vector adj[MAXN]; int val[MAXN]; bool vis[MAXN]; int f[MAXN][MAXN*2][2]; int n, k; int ans; void dfs(int u) { vis[u] = true; // init for (int i = 0; i <= k; ++i) f[u][i][0] = f[u][i][1] = val[u]; // dp for (int e = 0; e < adj[u].size(); ++e) { int v = adj[u][e]; if (vis[v]) continue; dfs(v); for (int i = k; i >= 1; --i) { for (int j = 1; j <= i; ++j) { if (j == 1) { int tmp1 = f[u][i-j][1] + f[v][j-1][0]; f[u][i][0] = max(f[u][i][0], tmp1); } else { int tmp1 = f[u][i-j][1] + f[v][j-1][0]; int tmp2 = f[u][i-j][0] + f[v][j-2][1]; f[u][i][0] = max(f[u][i][0], max(tmp1, tmp2)); f[u][i][1] = max(f[u][i][1], f[u][i-j][1] + f[v][j-2][1]); } } } } } int main(){ while (~scanf("%d %d", &n, &k)) { for (int i = 0; i <= n; ++i) adj[i].clear(); for (int i = 1; i <= n; ++i) scanf("%d", &val[i]); for (int i = 0; i < n - 1; ++i) { int u, v; scanf("%d%d", &u, &v); adj[u].push_back(v); adj[v].push_back(u); } memset(vis, 0, sizeof(vis)); memset(f, 0, sizeof(f)); dfs(1); printf("%d\n", f[1][k][0]); } return 0; }