#include<bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt")
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
#define DBG(a) cerr<< "line "<<__LINE__ <<" : "<< #a <<" --> "<<(a)<<endl
#define eps 1e-8
//#define eq(x,y) (fabs((x)-(y)) < eps)
using namespace std;
typedef long long ll;
typedef long long LL;
typedef long double Tf;
typedef pair<ll,ll>pii;
const ll mod = 998244353;
//const ll mod = 1e9+7;
//long double pi = acosl(-1);
const ll infl = 1e18+100;
const int inf = 1e9+100;
const int nmax = 1e5+50;
//const int MAXLG = log2(nmax)+1;
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
//typedef tree< ll, nullptr_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ost;


priority_queue<ll>pq[nmax];

void solve(int ces){
    int n;
    cin>>n;
    vector< vector<int> >g(n+1);
    vector<int>A(n+1);
    for(int i=1; i<=n; i++) cin>>A[i];
    for(int i=1; i<n; i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    ll tmpans = 0;
    auto dfs = [&](auto &dfs, int u, int p) -> void {
//        cout<<"dfs at "<<u<<endl;
        for(int v : g[u]) if(v!=p){
            dfs(dfs, v, u);
            if(pq[u].size() < pq[v].size())
                pq[u].swap(pq[v]);
            while(!pq[v].empty()){
                pq[u].push(pq[v].top());
                pq[v].pop();
            }
        }

        ll cur = A[u];
        while(pq[u].size() >= 2){
            if(cur >= pq[u].top()) {
                pq[u].push(cur);
                return;
            }
            cur -= pq[u].top();
            pq[u].pop();
            cur += pq[u].top();
            pq[u].pop();
        }
        if(pq[u].size()==1){
            if(pq[u].top() > cur){
                cur -= pq[u].top();
                pq[u].pop();
                tmpans += cur;
            }
            else{
                pq[u].push(cur);
            }
        }
        else{
            pq[u].push(cur);
        }
    };

    dfs(dfs, 1, 0);

    ll wholsum = accumulate(A.begin(), A.end(), 0LL);
    while(!pq[1].empty()){
        wholsum += pq[1].top();
        pq[1].pop();
        if(pq[1].empty()) wholsum -= tmpans;
        if(!pq[1].empty()){
            wholsum -= pq[1].top();
            pq[1].pop();
            if(pq[1].empty()) wholsum += tmpans;
        }
    }

    cout<<wholsum/2<<"\n";
}
/*
*/
int main(){
    ios::sync_with_stdio(false); cin.tie(0);

    int tc=1;
//    cin>>tc;
    for(int ces=1; ces<=tc; ces++){
        solve(ces);
    }
}