#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define ll long long
using namespace std;
typedef pair<ll,int> pii;

const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}

const int maxn=1e5+10;
int pos[maxn],par[maxn];
ll a[maxn];
vector<int>vect[maxn];
void prek(int x,int prv){

    par[x]=prv;
    for(int i=0;i<vect[x].size();i++){
        int id=vect[x][i];
        if(id==prv)continue;
        prek(id,x);
    }
}
int main(){


    ///freopen("test.txt","r",stdin);

    int n;
    scanf("%d",&n);
    ll sum=0;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        sum+=a[i];
    }
    for(int i=1;i<n;i++){
        int  u,v;
        scanf("%d %d",&u,&v);
        vect[u].pb(v);
        vect[v].pb(u);
    }

    prek(1,0);

    pos[0]=1;
    set<pii>st;
    for(int i=1;i<=n;i++){
        st.insert({-a[i],i});
    }

    ll rez=0;
    ll coef=1;
    while(st.size()){

        int x=(*st.begin()).ss;
        st.erase(st.begin());
        if(pos[x])continue;

        if(pos[par[x]]){
            rez+=coef*a[x];
            coef*=-1;
            pos[x]=1;
        }
        else{

            int y=par[x];
            st.erase({-a[y],y});
            a[y]-=a[x];
            st.insert({-a[y],y});
            pos[x]=1;

            for(int j=0;j<vect[x].size();j++){
                int id=vect[x][j];
                if(pos[id])continue;
                vect[y].pb(id);
                par[id]=y;
            }

        }

    }

    printf("%lld\n",(rez+sum)/2);

    return 0;
}