#include <bits/stdc++.h> using namespace std; const int maxn=2000; bool son[maxn][maxn]; int w[maxn]; int f[maxn]; int n; int dq[maxn]; int ans=0; int dfs(int ptr,int last_ptr){ if(ptr>n or ptr==0){ return 0; } else{ for(int i=0;i<maxn;i++){ if(i==last_ptr){ continue; } if(son[ptr][i]){ f[ptr]=max(f[ptr],dfs(i,ptr)+w[i]); } } } return f[ptr]; } int p=0; void find(int ptr,int last_ptr){ if(ptr>n or ptr==0){ return ; } else{ dq[p++]=w[ptr]; //cout<<ptr<<" "; int max_c=0; int max_n=0; for(int i=0;i<maxn;i++){ if(i==last_ptr){ continue; } if(son[ptr][i]){ if(f[i]>max_c){ max_c=f[i]; max_n=i; } } } find(max_n,ptr); } } void print(){ for(int i=0;i<p;i++){ cout<<dq[i]<<" "; } } int answer(){ int ans=0; for(int i=0;i<p;i++){ ans+=(i+1)*w[dq[i]]; } return ans; } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>w[i]; } for(int i=1;i<n;i++){ int a,b; cin>>a>>b; son[a][b]=true; son[b][a]=true; } int max_c=0; int max_n=0; for(int i=1;i<n;i++){ if(!f[i]){ int d=dfs(i,i); if(d>max_c){ max_c=d; max_n=i; } } } find(max_n,max_n); sort(dq,dq+p); cout<<endl<<answer(); } /* 0 1 1 0 */