#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=1e5+100;
vector <int> g[N];
vector <pii> y[N];
ll hd[N];
ll a[N],st[N],fn[N],ts=1;
ll sz[N];
ll par[N];
ll hi[N];
void dfssz(ll v,ll p){
par[v]=p;
sz[v]=1;
hi[v]=hi[p]+1;
for (auto u : g[v]){
if (u==p) continue;
dfssz(u,v);
sz[v]+=sz[u];
}
}
void dfshld(ll v,ll p,ll h){
hd[v]=h;
ll big=0;
st[v]=ts;
for (auto u : g[v]){
if (u==p) continue;
if (sz[u]>sz[big]) big=u;
}
if (big){
ts++;
dfshld(big,v,h);
}
for (auto u : g[v]){
if (u==p || u==big) continue;
ts++;
dfshld(u,v,u);
}
fn[v]=ts;
}
ll fen[N];
void add(ll idx,ll val){
for (;idx<N;idx+=idx & (-idx)){
fen[idx]+=val;
}
}
ll get(ll idx){
ll s=0;
for (;idx;idx-= idx & (-idx)){
s+=fen[idx];
}
return s;
}
ll solve(vector <pii> t){
ll s=0;
for (auto u : t){
s+=get(u.S-1)*u.F;
add(u.S,u.F);
}
for (auto u : t){
add(u.S,-u.F);
}
return s;
}
map <int,int> mp;
int32_t main(){
sync;
ll n;
cin >> n;
vector <int> com;
for (int i=1;i<=n;i++){
cin >> a[i];
com.pb(a[i]);
}
sort(com.begin(),com.end());
for (int i=0;i<com.size();i++){
mp[com[i]]=i+1;
}
for (int i=1;i<=n;i++){
a[i]=mp[a[i]];
}
vector <pii> yal;
for (int i=0;i<n-1;i++){
ll u,v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
yal.pb({u,v});
}
dfssz(1,1);
dfshld(1,1,1);
par[1]=0;
for (int i=0;i<n-1;i++){
ll v=yal[i].S;
ll z=v;
vector <pii> tt,t;
while(true){
ll k=hd[v];
// cout << v << " erjf " << k << endl;
while(y[k].size() && y[k].back().F<=hi[v]) tt.pb({y[k].back().F,y[k].back().S}),y[k].pop_back();
if (y[k].size()) tt.pb({hi[v],y[k].back().S});
y[k].pb({hi[v],a[z]});
v=par[k];
reverse(tt.begin(),tt.end());
for (int i=0;i<(ll)tt.size()-1;i++){
tt[i].F-=tt[i+1].F;
}
if (tt.size())
tt[tt.size()-1].F-=hi[par[k]];
for (auto u : tt) t.pb(u);
tt.clear();
if (k==1) break;
}
// reverse(t.begin(),t.end());
// for (auto u : t) cout << u.F << " " << u.S << " rwegr ";
// cout << " mrgrtg " << endl;
cout << solve(t) << endl;
}
for (int i=1;i<=n;i++){
// cout << hd[i] << endl;
}
}
/*
5
1 7 3 4 8
1 2
1 3
2 4
3 5
*/
