Nós da árvore

#include "bits/stdc++.h"
using namespace std;

const int OO = 1000000000;
const int ms = 20000;

int n, x;
vector<int> val, sz;
vector<int> G[ms];
vector<vector<int>> dp; // dp[ms][ms]

void init() {
    val.resize(n);
    sz.resize(n);
    dp = vector<vector<int>>(n + 1, vector<int>(x + 1, -OO));
    for(int i = 0; i < n; ++i)
        dp[i][0] = 0;
}

void dfs(int u, int p) {
    sz[u] = 1;
    for(const int &v : G[u]) {
        if(v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];

        int T = min(x, sz[u] - 1);

        vector<int> dp_u = dp[u];

        for(int a = 0; a <= T; ++a)
            for(int b = 0; b <= a; ++b)
                if(dp[v][b] != -OO && dp_u[a - b] != -OO)
                    dp[u][a] = max(dp[u][a], dp[v][b] + dp_u[a - b]);
    }
    dp[u][1] = max(dp[u][1], val[u]);
}

int main(){
    cin >> n >> x;

    init();

    for(int i = 0; i < n; ++i)
        cin >> val[i];

    for(int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    dfs(0, -1);

    if(dp[0][x] != -OO)
        cout << dp[0][x] << '\n';
    else
        cout << "impossivel\n";

    return 0;
}