#include <bits/stdc++.h> using namespace std; int n,ans; int a[410]; int b[410][410]; int f[410][410]; int t[410]; int v[410]; void dfs(int s,int now,int tot) { if(v[now]==1) { return; } t[tot++]=a[now]; sort(t,t+tot); int cnt=0; for(int i=0; i<tot; i++) { cnt+=t[i]*(i+1); } f[s][now]=max(f[s][now],cnt); for(int i=0; i<n; i++) { if(b[now][i]==1) { v[now]=1; dfs(s,i,tot+1); v[now]=0; } } } int main() { cin>>n; for(int i=0; i<n; i++) { cin>>a[i]; } for(int i=0; i<n-1; i++) { int t1,t2; cin>>t1>>t2; b[t1][t2]=b[t2][t1]=1; } for(int i=0; i<n; i++) { dfs(i,i,0); } for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { ans+=max(f[i][j],f[j][i]); } } cout<<ans<<endl; return 0; }