PTREE - VNOJ - Traceback of Knapsack on Tree

//Make CSP great again
//You're as beautiful as the day I lost you
//New year, best wishes
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 2e2;
vector<int> Adj[N + 1];
int c[N + 1], f[N + 1], Trace[N + 1][N + 1], n, m;
vector<int> dp[N + 1];
void read()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> c[i];
    }
    for (int i = 1; i < n; ++ i)
    {
        int u, v;
        cin >> u >> v;
        Adj[u].push_back(v);
        Adj[v].push_back(u);
    }
}
void DFS(int u, int p)
{
    f[u] = p;
    dp[u] = {0, c[u]};
    for (int v : Adj[u])
    {
        if (v == p)
        {
            continue;
        }
        DFS(v, u);
        vector<int> t(dp[u].size() + dp[v].size() - 1, -1e9);
        for (int i = 1; i < dp[u].size(); ++ i)
        {
            for (int j = 0; j < dp[v].size(); ++ j)
            {
                if (t[i + j] < dp[u][i] + dp[v][j])
                {
                    t[i + j] = dp[u][i] + dp[v][j];
                    Trace[v][i + j] = j;
                }
            }
        }
        t[0] = 0;
        swap(t, dp[u]);
    }
}
void Traceback(int u, int p, int a)
{
    if (a == 0)
    {
        return ;
    }
    reverse(Adj[u].begin(), Adj[u].end());
    for (int v : Adj[u])
    {
        if (v == p)
        {
            continue;
        }
        Traceback(v, u, Trace[v][a]);
        a -= Trace[v][a];
    }
    cout << u << ' ';
}
void solve()
{
    DFS(1, 0);
    int root = -1;
    for (int i = 1; i <= n; ++ i)
    {
        if (dp[i].size() > m)
        {
            if (root == -1 || dp[i][m] > dp[root][m])
            {
                root = i;
            }
        }
    }
    Traceback(root, f[root], m);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".out", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}