#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NEG_INF = -1e18;
int N, K;
vector<int> adj[200005];
ll p[200005];
// K <= 3, so in/out range 0..K, i.e., 0..3 max → size 4 is enough
ll dp[200005][5][5]; // [node][in 0..K][out 0..K]
bool did_biz[200005][5][5];
vector<tuple<int,int,int>> cc[200005][5][5];
int par[200005];
vector<int> order;
void solve() {
int KK = K; // max valid consecutive = K (K+1 fires)
for (int u = 1; u <= N; u++)
for (int i = 0; i <= KK; i++)
for (int o = 0; o <= KK; o++)
dp[u][i][o] = NEG_INF;
for (int idx = (int)order.size()-1; idx >= 0; idx--) {
int u = order[idx];
int parent = par[u];
vector<int> children;
for (int v : adj[u]) if (v != parent) children.push_back(v);
for (int in = 0; in <= KK; in++) {
// profit_no[out]: no biz at u, cur_out starts at 'in'
// profit_yes[out]: biz at u, cur_out starts at 0, profit = p[u]
vector<ll> pno(KK+1, NEG_INF), pyes(KK+1, NEG_INF);
vector<vector<tuple<int,int,int>>> cno(KK+1), cyes(KK+1);
pno[in] = 0;
pyes[0] = p[u];
for (int c : children) {
vector<ll> nno(KK+1, NEG_INF), nyes(KK+1, NEG_INF);
vector<vector<tuple<int,int,int>>> ncno(KK+1), ncyes(KK+1);
auto process = [&](vector<ll>& prof, vector<vector<tuple<int,int,int>>>& ch,
vector<ll>& nprof, vector<vector<tuple<int,int,int>>>& nch) {
for (int out = 0; out <= KK; out++) {
if (prof[out] == NEG_INF) continue;
// Skip child
if (nprof[out] < prof[out]) {
nprof[out] = prof[out];
nch[out] = ch[out];
}
// Visit child c
int in_c = out + 1;
if (in_c > KK) continue; // fired on arrival
for (int out_c = 0; out_c <= KK; out_c++) {
if (dp[c][in_c][out_c] == NEG_INF) continue;
int new_out = out_c + 1;
if (new_out > KK) continue; // fired on return
ll np = prof[out] + dp[c][in_c][out_c];
if (nprof[new_out] < np) {
nprof[new_out] = np;
nch[new_out] = ch[out];
nch[new_out].push_back({c, in_c, out_c});
}
}
}
};
process(pno, cno, nno, ncno);
process(pyes, cyes, nyes, ncyes);
pno = nno; cno = ncno;
pyes = nyes; cyes = ncyes;
}
// Store
for (int out = 0; out <= KK; out++) {
if (pno[out] != NEG_INF && pno[out] > dp[u][in][out]) {
dp[u][in][out] = pno[out];
did_biz[u][in][out] = false;
cc[u][in][out] = cno[out];
}
if (pyes[out] != NEG_INF && pyes[out] > dp[u][in][out]) {
dp[u][in][out] = pyes[out];
did_biz[u][in][out] = true;
cc[u][in][out] = cyes[out];
}
}
}
}
}
vector<int> route;
void reconstruct(int u, int in_state, int out_state) {
if (did_biz[u][in_state][out_state]) route.push_back(u);
for (auto& [c, in_c, out_c] : cc[u][in_state][out_state])
reconstruct(c, in_c, out_c);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> K;
for (int i = 0; i < N-1; i++) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= N; i++) cin >> p[i];
// Iterative DFS for order
{
stack<pair<int,int>> st;
st.push({1, 0});
while (!st.empty()) {
auto [u, parent] = st.top(); st.pop();
par[u] = parent;
order.push_back(u);
for (int v : adj[u]) if (v != parent) st.push({v, u});
}
}
solve();
// Root node: in=0, must do business at root (city 1 business is mandatory)
ll best = NEG_INF;
int best_out = -1;
for (int out = 0; out <= K; out++) {
if (did_biz[1][0][out] && dp[1][0][out] > best) {
best = dp[1][0][out];
best_out = out;
}
}
if (best_out == -1) {
for (int out = 0; out <= K; out++) {
if (dp[1][0][out] > best) {
best = dp[1][0][out];
best_out = out;
}
}
}
cout << best << "\n";
reconstruct(1, 0, best_out);
cout << route.size() << "\n";
for (int i = 0; i < (int)route.size(); i++) {
if (i) cout << " ";
cout << route[i];
}
cout << "\n";
return 0;
}
