#include "bits/stdc++.h"
using namespace std;
vector< vector<long long> > Grafo;
vector<long long> v, d, a;
vector<int> Final, Tour;
int Hay;
struct Valor{
long long Mayor_y_vuelvo, Mayor_y_no_vuelvo, Mayor_y_se_acaba_antes;
vector< pair<int, bool> > Seguir_si_vuelvo;
pair<int, bool> Seguir_si_no_vuelvo;
bool Existo;
};
vector< vector<Valor> > PD;
void DFS(int Nodo){
Hay--;
Final[Nodo] = Tour.size();
Tour.push_back(Nodo);
if(Hay == 0) return;
for(auto E: Grafo[Nodo]){
if(Hay == 0) return;
//cerr<<Nodo<<" "<<E<<"\n";
if(d[E] > d[Nodo] + v[E]){
d[E] = d[Nodo] + v[E];
DFS(E);
a[E] = Nodo;
Final[Nodo] = Tour.size();
Tour.push_back(Nodo);
}
}
}
Valor Resolver(int Nodo, int Anterior, bool Me_usaron){
//cerr<<Nodo + 1<<"\n";
if(PD[Nodo][Me_usaron].Existo) return PD[Nodo][Me_usaron];
PD[Nodo][Me_usaron].Existo = 1;
long long Suma = v[Nodo] * Me_usaron;
Valor Retorno;
if(Grafo[Nodo].size() == 1 and Nodo != 0){
Retorno.Mayor_y_vuelvo = Suma;
Retorno.Seguir_si_vuelvo = {{-2, 0}};
Retorno.Mayor_y_no_vuelvo = -2;
Retorno.Mayor_y_se_acaba_antes = -2;
return PD[Nodo][Me_usaron] = Retorno;
}
int i = -1;
vector< pair<long long, pair<int, bool> > > Mejores_que_vuelven, Mejores_que_se_quedan;
for(auto E: Grafo[Nodo]){
i++;
if(E == Anterior) continue;
Suma += v[E];
if(Me_usaron){
auto e0 = Resolver(E, Nodo, 0);
auto e1 = Resolver(E, Nodo, 1);
long long Mayor = max(max(e0.Mayor_y_se_acaba_antes, e1.Mayor_y_se_acaba_antes - v[E]), max(e0.Mayor_y_no_vuelvo, e1.Mayor_y_no_vuelvo - v[E]));
if(Mayor == e0.Mayor_y_se_acaba_antes) Mejores_que_se_quedan.push_back({e0.Mayor_y_se_acaba_antes, {i, 0}});
else if(Mayor == e1.Mayor_y_se_acaba_antes - v[E]) Mejores_que_se_quedan.push_back({e1.Mayor_y_se_acaba_antes - v[E], {i, 1}});
else if(Mayor == e0.Mayor_y_no_vuelvo) Mejores_que_se_quedan.push_back({e0.Mayor_y_no_vuelvo, {i, 0}});
else Mejores_que_se_quedan.push_back({e1.Mayor_y_no_vuelvo - v[E], {i, 1}});
if(e0.Mayor_y_vuelvo > e1.Mayor_y_vuelvo - v[E]) Mejores_que_vuelven.push_back({e0.Mayor_y_vuelvo, {i, 0}});
else Mejores_que_vuelven.push_back({e1.Mayor_y_vuelvo - v[E], {i, 1}});
} else {
auto e = Resolver(E, Nodo, 1);
if(e.Mayor_y_no_vuelvo > e.Mayor_y_se_acaba_antes) Mejores_que_se_quedan.push_back({e.Mayor_y_no_vuelvo - v[E], {i, 1}});
else Mejores_que_se_quedan.push_back({e.Mayor_y_se_acaba_antes - v[E], {i, 1}});
Mejores_que_vuelven.push_back({e.Mayor_y_vuelvo - v[E], {i, 1}});
}
}
sort(Mejores_que_vuelven.rbegin(), Mejores_que_vuelven.rend());
sort(Mejores_que_se_quedan.rbegin(), Mejores_que_se_quedan.rend());
while(Mejores_que_vuelven.size() > 3) Mejores_que_vuelven.pop_back();
Retorno.Mayor_y_se_acaba_antes = Mejores_que_se_quedan[0].first + Suma;
Retorno.Seguir_si_no_vuelvo = {Mejores_que_se_quedan[0].second};
Retorno.Mayor_y_vuelvo = Suma;
//cerr<<Nodo + 1<<" "<<Suma<<"\n";
if(!Me_usaron){
for(i = 0; i < 2 and i < Mejores_que_vuelven.size(); i++){
Retorno.Mayor_y_vuelvo += Mejores_que_vuelven[i].first;
Retorno.Seguir_si_vuelvo.push_back(Mejores_que_vuelven[i].second);
}
if(Mejores_que_vuelven.size() == 3){
Retorno.Mayor_y_no_vuelvo = Retorno.Mayor_y_vuelvo + Mejores_que_vuelven[2].first;
Retorno.Seguir_si_vuelvo.push_back(Mejores_que_vuelven[2].second);
} else {
Retorno.Mayor_y_no_vuelvo = -2;
}
return PD[Nodo][Me_usaron] = Retorno;
}
for(i = 0; i < 1 and i < Mejores_que_vuelven.size(); i++){
Retorno.Mayor_y_vuelvo += Mejores_que_vuelven[i].first;
Retorno.Seguir_si_vuelvo.push_back(Mejores_que_vuelven[i].second);
}
if(Mejores_que_vuelven.size() >= 2){
Retorno.Mayor_y_no_vuelvo = Retorno.Mayor_y_vuelvo + Mejores_que_vuelven[1].first;
Retorno.Seguir_si_vuelvo.push_back(Mejores_que_vuelven[1].second);
} else {
Retorno.Mayor_y_no_vuelvo = -2;
}
return PD[Nodo][Me_usaron] = Retorno;
}
vector<int> Recorrer;
void Recuperar(int Nodo, int Anterior, bool Me_usaron){
auto Actual = PD[Nodo][Me_usaron];
/*cerr<<Nodo + 1<<" "<<Anterior + 1<<" "<<Me_usaron<<"\n";
for(auto E: Actual.Seguir_si_vuelvo){
cerr<<Grafo[Nodo][E.first] + 1<<" ";
}
cerr<<"\n";
cerr<<Grafo[Nodo][Actual.Seguir_si_no_vuelvo.first] + 1<<"\n";*/
if(Grafo[Nodo].size() == 1 and Nodo != 0){
Recorrer.push_back(Nodo);
return;
}
if(Me_usaron) Recorrer.push_back(Nodo);
long long Mejor = max(max(Actual.Mayor_y_vuelvo, Actual.Mayor_y_no_vuelvo), Actual.Mayor_y_se_acaba_antes);
set<int> No_ir;
int Elijo;
if(Actual.Mayor_y_vuelvo == Mejor){
for(int i = 0; i < Actual.Seguir_si_vuelvo.size() and i < 2 - (int)Me_usaron; i++){
No_ir.insert(Actual.Seguir_si_vuelvo[i].first);
}
Elijo = 2;
} else if(Actual.Mayor_y_no_vuelvo == Mejor){
for(int i = 0; i < Actual.Seguir_si_vuelvo.size(); i++){
No_ir.insert(Actual.Seguir_si_vuelvo[i].first);
}
Elijo = 22;
} else {
No_ir.insert(Actual.Seguir_si_no_vuelvo.first);
Elijo = 222;
}
for(int i = 0; i < Grafo[Nodo].size(); i++){
if(Grafo[Nodo][i] == Anterior or No_ir.count(i)) continue;
Recorrer.push_back(Grafo[Nodo][i]);
}
if(Elijo == 2){
//cerr<<Nodo + 1<<" Llego 2.\n";
if(Me_usaron) Recuperar(Grafo[Nodo][Actual.Seguir_si_vuelvo[0].first], Nodo, Actual.Seguir_si_vuelvo[0].second);
else {
for(int i = 0; i < Actual.Seguir_si_vuelvo.size() and i < 2; i++){
if(i == 1){
Me_usaron = 1;
Recorrer.push_back(Nodo);
}
Recuperar(Grafo[Nodo][Actual.Seguir_si_vuelvo[i].first], Nodo, Actual.Seguir_si_vuelvo[i].second);
}
}
if(!Me_usaron) Recorrer.push_back(Nodo);
} else if(Elijo == 22){
//cerr<<Nodo + 1<<" Llego 22.\n";
for(int i = 0; i < Actual.Seguir_si_vuelvo.size(); i++){
if(i == 1 and !Me_usaron){
Me_usaron = 1;
Recorrer.push_back(Nodo);
}
Recuperar(Grafo[Nodo][Actual.Seguir_si_vuelvo[i].first], Nodo, Actual.Seguir_si_vuelvo[i].second);
}
} else {
//cerr<<Nodo + 1<<" Llego 222.\n";
for(int i = 0; i < Actual.Seguir_si_vuelvo.size(); i++){
if(i == 1 and !Me_usaron){
Me_usaron = 1;
Recorrer.push_back(Nodo);
}
Recuperar(Grafo[Nodo][Actual.Seguir_si_vuelvo[i].first], Nodo, Actual.Seguir_si_vuelvo[i].second);
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
long long m = 0;
cin>>n>>k;
Grafo.assign(n, {});
v.assign(n, 0);
d.assign(n, 2222222222222222);
a.assign(n, -2);
Valor Nada;
Nada.Existo = 0;
PD.assign(n, vector<Valor>(2, Nada));
Final.assign(n, 0);
Hay = n;
for(int i = 0; i < n - 1; i++){
int a, b;
cin>>a>>b;
a--;
b--;
Grafo[a].push_back(b);
Grafo[b].push_back(a);
}
for(int i = 0; i < n; i++){
cin>>v[i];
m += v[i];
}
if(k == 1){
d[0] = v[0];
DFS(0);
int p = 0;
m = 0;
for(int i = 0; i < n; i++){
if(d[i] > m){
m = d[i];
p = i;
}
}
vector<int> r;
cout<<m<<"\n";
while(p != -2){
r.push_back(p);
p = a[p];
}
reverse(r.begin(), r.end());
cout<<r.size()<<"\n";
for(auto E: r) cout<<E + 1<<" ";
return 0;
}
if(k == 3){
bitset<222222> Visitados;
d[0] = v[0];
DFS(0);
vector<int> r;
Visitados[0] = 1;
r.push_back(0);
Hay = n;
cout<<m<<"\n"<<n<<"\n";
n = Tour.size();
int c = 0;
for(int i = 1; i < n and Hay > 0; i++){
if(i == Final[Tour[i]] and !Visitados[Tour[i]]){
c = 0;
r.push_back(Tour[i]);
Visitados[Tour[i]] = 1;
Hay--;
} else if(c == 2){
c = 0;
r.push_back(Tour[i]);
Visitados[Tour[i]] = 1;
Hay--;
} else c++;
}
for(auto E: r) cout<<E + 1<<" ";
return 0;
}
auto Respuesta = Resolver(0, -2, 1);
//cerr<<Respuesta.Mayor_y_vuelvo<<" "<<Respuesta.Mayor_y_no_vuelvo<<" "<<Respuesta.Mayor_y_se_acaba_antes<<" ¿?\n";
//cerr<<"Terminado.\n";
cout<<max(max(Respuesta.Mayor_y_no_vuelvo, Respuesta.Mayor_y_vuelvo), Respuesta.Mayor_y_se_acaba_antes)<<"\n";
Recuperar(0, -2, 1);
cout<<Recorrer.size()<<"\n";
for(auto E: Recorrer) cout<<E + 1<<" ";
return 0;
}
