Submission #5771576

---

Source Code Expand

#include<bits/stdc++.h>
#include <queue> 
#include<map>
#define ll long long
#define ull unsigned long long 
#define ld long double
#define all(ar) ar.begin(), ar.end()
#define mp make_pair
#define sot(bello) bello.begin(),bello.end()
#define bitc  __builtin_popcountl
#define fr(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define frr(i,a,b) for (int i = (a), _b = (b); i >= _b; i--)
#define rep(i,n) for (int i = 0, _n = (n); i < _n; i++)
#define repr(i,n) for (int i = n - 1; i >= 0; i--)
#define fill(ar,val) memset(ar, val, sizeof(ar))
#define fill0(ar) fill((ar), 0)
#define MAXN   100010 
#define MOD 1000000007
#define debug(x) cout<<#x<<": "<<x<<endl
#define dbug(x) cout<<#x<<": "<<x<<" "
#define fi first
#define se second
#define arr1d(a,n) cout << #a << " : "; fr(_,1,n) cout << a[_] << ' '; cout << endl;
#define arr1d0(a,n) cout << #a << " : "; rep(_,n) cout << a[_] << ' '; cout << endl;
#define arr2d(a,n,m) cout << #a << " :" << endl; fr(_,1,n) {fr(__,1,m) cout << a[_][__] << ' '; cout << endl;}
#define arr2d0(a,n,m) cout << #a << " :" << endl; rep(_,n) {rep(__,m) cout << a[_][__] << ' '; cout << endl;}

# define INF LLONG_MAX
const int dx[]={0,0,-1,1},dy[]={-1,1,0,0};



using namespace std;

vector<ll> co(10010);
ll n,sum;
// Dfs search

void dfs(std::vector<ll> v[],ll s,bool visited[],ll &cc,ll ar[])
{
	visited[s]=true;
    co[s]=ar[cc];
    cc--;
  for (ll i = 0; i < v[s].size(); ++i)
  {
  	if(!visited[v[s][i]] )
      
  	{ 
		dfs(v,v[s][i],visited,cc,ar);

  	}

  }
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
vector<ll> v[n+1];
rep(i,n-1){
    ll a,b;
    cin>>a>>b;
    v[a].push_back(b);
    v[b].push_back(a);
}
ll c[n];
rep(i,n){
    cin>>c[i];
    sum+=c[i];
}
sort(c,c+n);
vector<pair<ll,ll> > vec;
fr(i,1,n){
  vec.push_back(mp(v[i].size(),i));
}
sort(sot(vec));
ll ind=vec[n-1].second;
bool visited[n+1];
ll cc=n-1;
dfs(v,ind,visited,cc,c);
cout<<sum-c[n-1]<<endl;
fr(i,1,n){
    cout<<co[i]<<" ";
}
cout<<endl;
}

Submission Info

Judge Result