1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <string> 8 #include <queue> 9 #include <stack>10 #include <vector>11 #include <map>12 #include <set>13 #include <functional>14 #include <cctype>15 #include <time.h>16 17 using namespace std;18 19 const int INF = 1<<30;20 21 struct Graph {22     static const int MAXN = 111;23     static const int MAXM = MAXN*2;24 25     int head[MAXN];26     int next[MAXM], to[MAXM], use;27 28     int val[MAXN], size[MAXN];29     int m;30 31     void init(int n, int m) {32         memset(head, -1, sizeof(head));33         use = 0;34 35         this->m = m;36         for (int i = 1; i <= n; i++) scanf("%d", &val[i]);37         int u, v;38         for (int i = 1; i < n; i++) {39             scanf("%d%d", &u, &v);40             addEdge(u, v);41             addEdge(v, u);42         }43     }44 45     inline void addEdge(int u, int v) {46         next[use] = head[u];47         to[use] = v;48         head[u] = use++;49     }50 51     int dp[MAXN][MAXN];52 53     void dfs(int u, int pre) {54         memset(dp[u], 0, sizeof(dp[u]));55         size[u] = 1;56         for (int p = head[u]; p != -1; p = next[p]) {57             int v = to[p];58             if (v==pre) continue;59             dfs(v, u);60             size[u] += size[v];61         }62         dp[u][1] = val[u];63         for (int p = head[u]; p != -1; p = next[p]) {64             int v = to[p];65             if (v==pre) continue;66             for (int i = size[u]; i > 0; i--)67                 for (int j = 1; j <= size[v]; j++) {68                     if (i+j>size[u]) break;69                     dp[u][i+j] = max(dp[u][i+j], dp[u][i]+dp[v][j]);70                 }71         }72     }73 74     void solve() {75         int ans = 0;76         dfs(1, 1);77         for (int i = 1; i <= m; i++)78             ans = max(ans, dp[1][i]);79         printf("%d\n", ans);80     }81 }solver;82 83 int main() {84     #ifdef Phantom0185         freopen("1055.txt", "r", stdin);86     #endif //Phantom0187 88     int n, m;89     while (scanf("%d%d", &n, &m)!=EOF) {90         solver.init(n, m);91         solver.solve();92     }93 94     return 0;95 }