#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
using namespace std;
#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int n;
vector<int> vect, depth, par, sz, head, ft;
vector<vector<int> > graph;
void dfs(int node, int p, int d){
depth[node]=d;
par[node]=p;
if (graph[node].size()>1&&graph[node][0]==p)swap(graph[node][0], graph[node][1]);
for (auto &num:graph[node])if (num!=p){
dfs(num, node, d+1);
sz[node]+=sz[num];
if (sz[num]>sz[graph[node][0]])swap(num, graph[node][0]);
}
}
void hld(int node, int p){
for (auto num:graph[node])if (num!=p){
if (num==graph[node][0])head[num]=head[node];
else head[num]=num;
hld(num, node);
}
}
int query(int i){
int res=0;
for (;i;i-=i&-i)res+=ft[i];
return res;
}
void up(int i, int v){
for (;i<ft.size();i+=i&-i)ft[i]+=v;
}
int calc(vector<pii> vect){
vector<int> ord;
for (auto a:vect)ord.pb(a.fi);
sort(ord.begin(), ord.end());
ord.erase(unique(ord.begin(), ord.end()), ord.end());
for (int i=0; i<vect.size(); ++i)vect[i].fi=lower_bound(ord.begin(), ord.end(), vect[i].fi)-ord.begin()+1;
ft.clear();
ft.resize(ord.size()+1, 0);
int res=0;
for (auto c:vect){
res+=(query(ord.size())-query(c.fi))*c.se;
up(c.fi, c.se);
}
return res;
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
vect.resize(n+1);
graph.resize(n+1);
sz.resize(n+1, 1);
par.resize(n+1, 0);
head.resize(n+1, 0);
depth.resize(n+1);
for (int i=1; i<=n; ++i)cin>>vect[i];
vector<int> ord;
for (int i=1, a, b; i<n; ++i){
cin>>a>>b;
ord.pb(b);
graph[a].pb(b);
graph[b].pb(a);
}
dfs(1, 0, 1);
head[1]=1;
hld(1, 0);
vector<stack<pii> > st(n+1);
for (auto c:ord){
int cc=vect[c];
vector<pii> res;
while (c){
int d=depth[c]-depth[head[c]]+1, t=0;
c=head[c];
vector<pii> temp;
while (st[c].size()&&st[c].top().se<=d){
temp.pb(mp(st[c].top().fi, st[c].top().se-t));
t=st[c].top().se;
st[c].pop();
}
if (st[c].size())temp.pb(mp(st[c].top().fi, d-t));
st[c].push(mp(cc, d));
reverse(temp.begin(), temp.end());
for (auto a:temp)res.pb(a);
c=par[c];
}
reverse(res.begin(), res.end());
cout<<calc(res)<<"\n";
}
}
