#pragma GCC optimize("Ofast", "unroll-loops")
#include<bits/stdc++.h>
using namespace std; using ll = long long;
#define For(i, j, k) for ( int i = (j) ; i <= (k) ; i++ )
#define Fol(i, j, k) for ( int i = (j) ; i >= (k) ; i-- )
int n, k, u, v, a[200009]; ll ans; vector < int > g[200009], res;
namespace k1
{
	int fa[200009], p; ll dep[200009];
	inline void dfs(int u, int fa = 0)
	{
		k1::fa[u] = fa, dep[u] = dep[fa] + a[u];
		for ( int i : g[u] ) if ( i != fa ) dfs(i, u);
	}
	inline void slv()
	{
		dfs(1), p = max_element(dep + 1, dep + n + 1) - dep, ans = dep[p];
		while ( p != 1 ) res.push_back(p), p = fa[p];
		res.push_back(1), reverse(res.begin(), res.end());
	}
}
namespace k3
{
	inline void dfs(int u, int fa = 0, int dep = 0)
	{
		if ( ~dep & 1 ) res.push_back(u);
		for ( int i : g[u] ) if ( i != fa ) dfs(i, u, dep + 1);
		if (  dep & 1 ) res.push_back(u);
	}
	inline void slv() { ans = accumulate(a + 1, a + n + 1, 0ll), dfs(1); }
}
namespace k2
{
#define fi first
#define se second
	constexpr ll inf = numeric_limits < ll >::max() >> 2; using P = pair < ll, int >;
	using T = array < P, 3 >; using E = tuple < int, int, int >; using O = pair < ll, E >;
	O dp[200009][2][2]; ll s; T mx[2][2]; int lim;
	inline void upd(O &x, const O &y) { if ( x.fi < y.fi ) x = y; }
	inline void upd(T &x, const P &y)
	{
		if ( y.fi > x[0].fi ) x[2] = x[1], x[1] = x[0], x[0] = y;
		else if ( y.fi > x[1].fi ) x[2] = x[1], x[1] = y;
		else if ( y.fi > x[2].fi ) x[2] = y;
	}
	inline void dfs(int u, int fa = 0)
	{
		if ( fa ) g[u].erase(find(g[u].begin(), g[u].end(), fa));
		for ( int i : g[u] ) dfs(i, u);
		s = a[u];
		for ( int i : g[u] ) s += a[i];
		For(i, 0, 1) For(j, 0, 1)
		{
			fill(mx[i][j].begin(), mx[i][j].end(), P(-inf, 0));
			for ( int k : g[u] ) upd(mx[i][j], P(dp[k][i][j].fi - a[k], k));
		}
		for ( int i : g[u] ) upd(dp[u][0][0], O(a[u] + dp[i][1][0].fi, E(i, 0, 0)));
		if ( (int)g[u].size() > 1 ) For(i, 0, 1) For(j, 0, 1) if ( mx[1][1][i].se != mx[0][0][j].se )
			upd(dp[u][0][0], O(s + mx[1][1][i].fi + mx[0][0][j].fi, E(mx[1][1][i].se, mx[0][0][j].se, 0)));
		if ( (int)g[u].size() ) upd(dp[u][0][1], O(s + mx[1][1][0].fi, E(mx[1][1][0].se, 0, 0)));
		upd(dp[u][1][0], O(dp[u][0][0].fi, E(1, 0, 0)));
		if ( (int)g[u].size() > 1 ) For(i, 0, 1) For(j, 0, 1) if ( mx[0][1][i].se != mx[1][0][j].se )
			upd(dp[u][1][0], O(s + mx[0][1][i].fi + mx[1][0][j].fi, E(mx[0][1][i].se, mx[1][0][j].se, 0)));
		if ( (int)g[u].size() > 2 ) For(i, 0, 2) For(j, 0, 2) For(k, 0, 2) if ( mx[0][1][i].se != mx[1][1][j].se && mx[0][1][i].se != mx[0][0][k].se && mx[1][1][j].se != mx[0][0][k].se )
			upd(dp[u][1][0], O(s + mx[0][1][i].fi + mx[1][1][j].fi + mx[0][0][k].fi, E(mx[0][1][i].se, mx[1][1][j].se, mx[0][0][k].se)));
		if ( (int)g[u].size() ) upd(dp[u][1][1], O(s + mx[0][1][0].fi, E(mx[0][1][0].se, 0, 0)));
	}
	inline void out(int u, int x, int y)
	{
		const E &nw = dp[u][x][y].se;
		if ( !get<0>(nw) ) { res.push_back(u); return; }
		if ( !x && !y )
		{
			res.push_back(u);
			if ( !get<1>(nw) ) out(get<0>(nw), 1, 0);
			else
			{
				out(get<0>(nw), 1, 1);
				for ( int i : g[u] ) if ( i != get<0>(nw) && i != get<1>(nw) ) res.push_back(i);
				out(get<1>(nw), 0, 0);
			}
		}
		if ( !x &&  y )
		{
			res.push_back(u), out(get<0>(nw), 1, 1);
			for ( int i : g[u] ) if ( i != get<0>(nw) ) res.push_back(i);
		}
		if (  x && !y )
		{
			if ( !get<1>(nw) ) out(u, 0, 0);
			else if ( !get<2>(nw) )
			{
				for ( int i : g[u] ) if ( i != get<0>(nw) && i != get<1>(nw) ) res.push_back(i);
				out(get<0>(nw), 0, 1), res.push_back(u), out(get<1>(nw), 1, 0);
			}
			else
			{
				for ( int i : g[u] ) if ( i != get<0>(nw) && i != get<1>(nw) && i != get<2>(nw) ) res.push_back(i);
				out(get<0>(nw), 0, 1), res.push_back(u), out(get<1>(nw), 1, 1), out(get<2>(nw), 0, 0);
			}
		}
		if (  x &&  y )
		{
			for ( int i : g[u] ) if ( i != get<0>(nw) ) res.push_back(i);
			out(get<0>(nw), 0, 1), res.push_back(u);
		}
	}
	inline void slv()
	{
		For(i, 1, n) For(j, 0, 1) For(k, 0, 1) dp[i][j][k] = O(a[i], E(0, 0, 0));
		dfs(1);
		if ( dp[1][0][0].fi > dp[1][0][1].fi ) ans = dp[1][0][0].fi, out(1, 0, 0);
		else                                   ans = dp[1][0][1].fi, out(1, 0, 1);
	}
#undef fi
#undef se
}
int main()
{
	// freopen("jump.in", "r", stdin), freopen("jump.out", "w", stdout);
	cin.tie(nullptr) -> sync_with_stdio(false);
	cin >> n >> k;
	For(i, 2, n) cin >> u >> v, g[u].push_back(v), g[v].push_back(u);
	For(i, 1, n) cin >> a[i];
	k == 1 ? k1::slv() : k == 3 ? k3::slv() : k2::slv();
	cout << ans << '\n' << res.size() << '\n';
	for ( int i : res ) cout << i << " \n"[i == res.back()];
	return 0;
}