#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const int MAXN = 200000 + 5;
int N, K;
vector<int> g[MAXN];
ll profit[MAXN];
vector<int> answer_path;
ll answer_profit = 0;
/* ---------- Common DFS utilities ---------- */
int parent[MAXN];
int depth[MAXN];
void dfs_init(int u, int p) {
parent[u] = p;
for (int v : g[u]) {
if (v == p) continue;
depth[v] = depth[u] + 1;
dfs_init(v, u);
}
}
/* ---------- K = 1 : Longest path from root ---------- */
ll best_sum_k1 = 0;
vector<int> best_path_k1;
void dfs_k1(int u, int p, ll cur_sum, vector<int> &cur_path) {
cur_sum += profit[u];
cur_path.push_back(u);
if (cur_sum > best_sum_k1) {
best_sum_k1 = cur_sum;
best_path_k1 = cur_path;
}
for (int v : g[u]) {
if (v == p) continue;
dfs_k1(v, u, cur_sum, cur_path);
}
cur_path.pop_back();
}
/* ---------- K = 3 : Visit all nodes ---------- */
vector<int> path_k3;
void dfs_k3(int u, int p) {
path_k3.push_back(u);
for (int v : g[u]) {
if (v == p) continue;
dfs_k3(v, u);
path_k3.push_back(u); // return
}
}
/* ---------- K = 2 : Placeholder (to be filled next) ---------- */
void solve_k2() {
// This is where dp1, dp2, dp3 tree DP will go.
// It is too large to safely generate in the same message.
// We will implement this in the next step.
cout << "K = 2 solver not yet implemented.\n";
exit(0);
}
/* ---------- Main ---------- */
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> K;
for (int i = 1; i <= N; i++) {
cin >> profit[i];
}
for (int i = 1; i < N; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs_init(1, 0);
if (K == 1) {
vector<int> cur;
dfs_k1(1, 0, 0, cur);
cout << best_sum_k1 << "\n";
for (int x : best_path_k1) cout << x << " ";
cout << "\n";
}
else if (K == 3) {
dfs_k3(1, 0);
ll total = 0;
vector<int> used(N + 1, 0);
for (int x : path_k3) {
if (!used[x]) {
total += profit[x];
used[x] = 1;
}
}
cout << total << "\n";
for (int x : path_k3) cout << x << " ";
cout << "\n";
}
else if (K == 2) {
solve_k2(); // real implementation will be added next
}
return 0;
}
