#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define pb push_back #define eb emplace_back #define ppc __builtin_popcount using namespace std; typedef long long ll; typedef __int128 i128; typedef long double db; typedef unsigned long long ull; typedef unsigned int uint; const int maxn=1e6+10,P=998244353; const ll inf=1e18; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,k,a[maxn],fa[maxn];ll sm[maxn]; vector<int>E[maxn]; void dfs(int u){ sm[u]=sm[fa[u]]+a[u]; for(int x:E[u])if(x!=fa[u])fa[x]=u,dfs(x); } void dfs2(int u){ printf("%d ",u); for(int x:E[u])if(x!=fa[u]){ for(int y:E[x])if(y!=u)dfs2(y); printf("%d ",x); } } ll dp[maxn][4]; vector<pi>out[maxn][4]; using pil=pair<ll,int>; struct nd{ pil t[4]; void init(){up(i,0,3)t[i]={0,-1};} void add(pil x){ up(i,0,3)if(x>=t[i]){ down(j,2,i)t[j+1]=t[j]; t[i]=x;return; } } }A[4]; bool same(vector<int>v){ up(i,0,v.size()-1) up(j,i+1,v.size()-1) if((~v[i])&&v[i]==v[j])return 1; return 0; } void dfs3(int u){ for(int x:E[u])if(x!=fa[u])dfs3(x); pil mx={0,-1},mx2={0,-1}; up(i,0,3)A[i].init(); for(int x:E[u])if(x!=fa[u]){ mx=max(mx,{dp[x][2],x});mx2=max(mx2,{dp[x][0],x}); up(j,0,3)A[j].add({dp[x][j]-a[x],x}); } dp[u][0]=mx.p1+a[u];out[u][0].eb(u,-1);if(~mx.p2)out[u][0].eb(mx.p2,2); ll s=a[u];for(int x:E[u])if(x!=fa[u])s+=a[x]; up(i,0,3)up(j,0,3){ if(same({A[3].t[i].p2,A[0].t[j].p2}))continue; if(s+A[3].t[i].p1+A[0].t[j].p1>dp[u][0]){ dp[u][0]=s+A[3].t[i].p1+A[0].t[j].p1; out[u][0].clear();out[u][0].eb(u,-1); int p=A[3].t[i].p2,q=A[0].t[j].p2; if(~p)out[u][0].eb(p,3); for(int x:E[u])if(x!=fa[u]&&x!=p&&x!=q)out[u][0].eb(x,-1); if(~q)out[u][0].eb(q,0); } } dp[u][1]=s+A[3].t[0].p1; out[u][1].eb(u,-1); if(~A[3].t[0].p2)out[u][1].eb(A[3].t[0].p2,3); for(int x:E[u])if(x!=fa[u]&&x!=A[3].t[0].p2)out[u][1].eb(x,-1); dp[u][2]=mx2.p1;if(~mx2.p2)out[u][2].eb(mx2.p2,0); up(i,0,3)up(j,0,3){ if(same({A[1].t[i].p2,A[2].t[j].p2}))continue; if(s+A[1].t[i].p1+A[2].t[j].p1>dp[u][2]){ dp[u][2]=s+A[1].t[i].p1+A[2].t[j].p1; out[u][2].clear();int p=A[1].t[i].p2,q=A[2].t[j].p2; for(int x:E[u])if(x!=fa[u]&&x!=p&&x!=q)out[u][2].eb(x,-1); if(~p)out[u][2].eb(p,1);out[u][2].eb(u,-1); if(~q)out[u][2].eb(q,2); } } up(i,0,3)up(j,0,3)up(k,0,3){ if(same({A[1].t[i].p2,A[3].t[j].p2,A[0].t[k].p2}))continue; if(s+A[1].t[i].p1+A[3].t[j].p1+A[0].t[k].p1>dp[u][2]){ dp[u][2]=s+A[1].t[i].p1+A[3].t[j].p1+A[0].t[k].p1; out[u][2].clear();int p=A[1].t[i].p2,q=A[3].t[j].p2,r=A[0].t[k].p2; for(int x:E[u])if(x!=fa[u]&&x!=p&&x!=q&&x!=r)out[u][2].eb(x,-1); if(~p)out[u][2].eb(p,1);out[u][2].eb(u,-1); if(~q)out[u][2].eb(q,3);if(~r)out[u][2].eb(r,0); } } dp[u][3]=s+A[1].t[0].p1;int p=A[1].t[0].p2; for(int x:E[u])if(x!=fa[u]&&x!=p)out[u][3].eb(x,-1); if(~p)out[u][3].eb(p,1);out[u][3].eb(u,-1); } int stk[maxn],top; void dfs4(int u,int op){ if(op==-1)return stk[++top]=u,void(); for(auto [x,y]:out[u][op])dfs4(x,y); } void slv(){ n=read(),k=read(); up(i,1,n-1){ int x=read(),y=read(); E[x].eb(y),E[y].eb(x); } up(i,1,n)a[i]=read();dfs(1); if(k==1){ int id=max_element(sm+1,sm+n+1)-sm;printf("%lld\n",sm[id]); vector<int>v;for(;id;id=fa[id])v.eb(id); reverse(v.begin(),v.end());printf("%lu\n",v.size()); for(int x:v)printf("%d ",x); }else if(k==2){ dfs3(1),dfs4(1,0);printf("%lld\n%d\n",dp[1][0],top); up(i,1,top)printf("%d ",stk[i]); }else{ printf("%lld\n%d\n",accumulate(a+1,a+n+1,0ll),n);dfs2(1); } } int main(){ // freopen("trader.in","r",stdin),freopen("trader.out","w",stdout); // int t=read();while(t--)slv(); slv(); return 0; }