#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]){//1 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]){//0 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]){//2 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; }