#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]; 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); dp[p][1]=max(dp[p][1],w[p]+dp[x][1]); s.insert({dp[x][1],x}); } for(int x:e[p]){//0 if(x==fa[p])continue; dp[p][0]=max(dp[p][0],dp[x][2]+v[x]); auto it=s.rbegin(); if(it->second==x){ if(s.size()==1)dp[p][0]=max(dp[p][0],dp[x][2]+w[p]); else it++,dp[p][0]=max(dp[p][0],dp[x][0]+it->first+w[p]); } else dp[p][0]=max(dp[p][0],dp[x][0]+it->first+w[p]); } for(int x:e[p]){//2 if(x==fa[p])continue; dp[p][2]=max(dp[p][2],dp[x][2]+v[x]); auto it=s.rbegin(),it1=it,it2=it; // cout<<p<<" "<<it->first<<" "<<it->second<<endl; if(s.size()==1){ dp[p][2]=max(dp[p][2],dp[x][2]+w[p]); continue; } if(s.size()>=2){ it1++; if(it->second==x)dp[p][2]=max(dp[p][2],dp[x][2]+it1->first+w[p]); else dp[p][2]=max(dp[p][2],dp[x][2]+it->first+w[p]); // continue; } 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; dp[p][2]=max(dp[p][2],res); } } } void slv(){ dfs(1); for(int i=2;i<=n;i++)w[fa[i]]+=v[i]; calc(1); // for(int i=1;i<=n;i++)cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<endl; cout<<dp[1][0]+v[1]<<endl<<1<<endl<<1; return; } }; void slv(){ read2(n,k); for(int i=1,u,v;i<n;i++){ read2(u,v); // cout<<u<<" "<<v<<endl; e[u].push_back(v); e[v].push_back(u); } for(int i=1;i<=n;i++)read(v[i]); // for(int i=1;i<=n;i++){ // for(int x:e[i])cout<<x<<" ";cout<<endl; // } if(k==1)sol1().slv(); else if(k==2)sol2().slv(); } signed main(){ slv(); return 0; }