#include<bits/stdc++.h> #define int unsigned long long void read(int&x){x=0;char c=getchar();for(;!isdigit(c);c=getchar());for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);} #define read2(a,b)read(a),read(b) using namespace std;int n,k,v[200005];vector<int>e[200005],ans;struct sol1{int fa[200005],dp[200005],son[200005];void dfs(int p){for(int x:e[p]){if(x==fa[p])continue;fa[x]=p;dp[x]=dp[p]+::v[x];dfs(x);}}void slv(){dp[1]=v[1];dfs(1);int mx=1;for(int i=1;i<=n;i++)if(dp[mx]<dp[i])mx=i;cout<<dp[mx]<<endl;while(mx!=1){son[fa[mx]]=mx;mx=fa[mx];}while(son[mx]){ans.push_back(mx);mx=son[mx];}ans.push_back(mx);cout<<ans.size()<<endl;for(int x:ans)cout<<x<<" ";cout<<endl;return;}};struct sol2{int fa[200005],w[200005],dp[200005][3];vector<pair<int,int>>pre[200005][3];void dfs(int p){for(int x:e[p]){if(x==fa[p])continue;fa[x]=p;dfs(x);}}void calc(int p){set<pair<int,int>>s;for(int x:e[p]){if(x==fa[p])continue;calc(x);if(dp[p][1]<w[p]+dp[x][1])dp[p][1]=w[p]+dp[x][1],pre[p][1]={{x,1}};s.insert({dp[x][1],x});}for(int x:e[p]){if(x==fa[p])continue;if(dp[p][0]<dp[x][2]+v[x])dp[p][0]=dp[x][2]+v[x],pre[p][0]={{x,2}};dp[p][0]=max(dp[p][0],dp[x][2]+v[x]);auto it=s.rbegin();if(it->second==x){if(s.size()==1){if(dp[p][0]<dp[x][2]+w[p])dp[p][0]=dp[x][2]+w[p],pre[p][0]={{x,2}};}else{it++;if(dp[p][0]<dp[x][0]+it->first+w[p])dp[p][0]=dp[x][0]+it->first+w[p],pre[p][0]={{it->second,1},{x,0}};}}else{if(dp[p][0]<dp[x][0]+it->first+w[p])dp[p][0]=dp[x][0]+it->first+w[p],pre[p][0]={{it->second,1},{x,0}};}}for(int x:e[p]){if(x==fa[p])continue;if(dp[p][2]<dp[x][2]+v[x])dp[p][2]=dp[x][2]+v[x],pre[p][2]={{x,2}};auto it=s.rbegin(),it1=it,it2=it;if(s.size()==1){if(dp[p][2]<dp[x][2]+w[p])dp[p][2]=dp[x][2]+w[p],pre[p][2]={{x,2}};dp[p][2]=max(dp[p][2],dp[x][2]+w[p]);continue;}if(s.size()>=2){it1++;if(it->second==x){if(dp[p][2]<dp[x][2]+it1->first+w[p])dp[p][2]=dp[x][2]+it1->first+w[p],pre[p][2]={{it1->second,1},{x,2}};}else{if(dp[p][2]<dp[x][2]+it->first+w[p])dp[p][2]=dp[x][2]+it->first+w[p],pre[p][2]={{it->second,1},{x,2}};}}if(s.size()>=3){it2++,it2++;int res=dp[x][0]+w[p];if(it->second==x)res+=it1->first+it2->first;else if(it1->second==x)res+=it->first+it2->first;else res+=it->first+it1->first;if(dp[p][2]<res){dp[p][2]=res;pre[p][2].clear();if(it->second==x)pre[p][2]={{it1->second,1},{it2->second,1},{x,0}};else if(it1->second==x)pre[p][2]={{it->second,1},{it2->second,1},{x,0}};else pre[p][2]={{it->second,1},{it1->second,1},{x,0}};}}}}void prt1(int x,int y){if(pre[x][y].empty()){ans.push_back(x);return;}int z=pre[x][1][0].first;if(y==0){ans.push_back(x);prt1(z,1);for(int s:e[x]){if(s==fa[x])continue;if(s==z)continue;ans.push_back(s);}}else{for(int s:e[x]){if(s==fa[x])continue;if(s==z)continue;ans.push_back(s);}prt1(z,0);ans.push_back(x);}}void prt(int x,int y){if(y==0){ans.push_back(x);if(pre[x][y].empty())return;if(pre[x][y].size()==1){auto[xx,yy]=pre[x][y][0];prt(xx,2);return;}set<int>son;for(auto[xx,yy]:pre[x][y])son.insert(xx);prt1(pre[x][y][0].first,1);for(int s:e[x]){if(s==fa[x])continue;if(son.count(s))continue;ans.push_back(s);}prt(pre[x][y][1].first,0);return;}if(pre[x][y].empty()){ans.push_back(x);return;}if(pre[x][y].size()==1){auto[xx,yy]=pre[x][y][0];ans.push_back(x);prt(xx,2);return;}set<int>son;for(auto[xx,yy]:pre[x][y])son.insert(xx);for(int s:e[x]){if(s==fa[x])continue;if(son.count(s))continue;ans.push_back(s);}if(pre[x][y].size()==2){prt1(pre[x][y][0].first,0);ans.push_back(x);prt(pre[x][y][1].first,2);return;}prt1(pre[x][y][0].first,0);ans.push_back(x);prt1(pre[x][y][1].first,1);prt(pre[x][y][2].first,0);return;}void slv(){dfs(1);for(int i=2;i<=n;i++)w[fa[i]]+=v[i];calc(1);cout<<dp[1][0]+v[1]<<endl;prt(1,0);cout<<ans.size()<<endl;for(int x:ans)cout<<x<<" ";return;}};struct sol3{void dfs(int p,int f=0){cout<<p<<" ";for(int x:e[p]){if(x==f)continue;for(int y:e[x]){if(y==p)continue;dfs(y,x);}cout<<x<<" ";}}void slv(){int ans=0;for(int i=1;i<=n;i++)ans+=v[i];cout<<ans<<endl<<n<<endl;dfs(1);return;}};void slv(){read2(n,k);for(int i=1,u,v;i<n;i++){read2(u,v);e[u].push_back(v);e[v].push_back(u);}for(int i=1;i<=n;i++)read(v[i]);if(k==1)sol1().slv();else if(k==2)sol2().slv();else sol3().slv();}signed main(){slv();return 0;}