RT

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,b[1000005];
struct jjj{
    int a,f,z,id,in;
}ak[1000005];
signed main(){
    scanf("%lld",&n);
    for(int i(1);i<=n;i++)
    scanf("%lld",&ak[i].a),ak[i].id=i,b[i]=ak[i].a;
    for(int i(1);i<n;i++)
    scanf("%lld%lld",&ak[i].f,&ak[i].z),ak[ak[i].f].in++,ak[ak[i].z].in++;
    sort(b+1,b+n+1);
    /*for(int i(1);i<=n;i++)
    printf("%lld ",ak[i].in);
    printf("\n");*/
    int k1=ak[(1+n)/2].a,k2=ak[(1+n)/2+1].a;
    long long ans1=0,ans2=0;
    for(int i(1);i<=n;i++)
    ans1+=ak[ak[i].id].in*abs(ak[ak[i].id].a-k1);
    for(int i(1);i<=n;i++)
    ans2+=ak[ak[i].id].in*abs(ak[ak[i].id].a-k2);
    /*if(n&1)
    cout<<ans1;
    else*/
    cout<<min(ans1,ans2);
    return 0;
}