#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define piii pair<pii, int>
const int N = 100505;
int ch[N] , pai[N] , C[N] , sz[N], in[N] , tempo = 0 , rinv[N + 100];
vector<int> adj[N];
vector<pii> edge;
deque<piii> Sx[N];
int n;
vector<pii> elements;
void dfs(int x , int y){
sz[x] = 1 ;
pai[x] = -1;
if(x != y) pai[x] = y;
for(auto &p : adj[x]){
if(p == y) continue;
dfs(p, x);
sz[x] += sz[p];
if(adj[x][0] == y || sz[adj[x][0]] < sz[p]) swap(p, adj[x][0]);
}
}
void dfs_hld(int x , int y){
in[x] = ++tempo;
if(x == y) ch[x] = 1;
rinv[tempo] = x;
for(auto p : adj[x]){
if(p == y) continue;
if(p == adj[x][0]) ch[p] = ch[x];
else ch[p] = p;
dfs_hld(p, x);
}
}
void getX(int x){
vector<pii> selements;
for(auto p : Sx[ch[x]]){
if(p.F.S <= in[x]){
selements.push_back(pii(p.S , p.F.S - p.F.F +1));
}
else if(p.F.F <= in[x]){
selements.push_back(pii(p.S , in[x] - p.F.F + 1));
}
else break;
}
reverse(selements.begin() , selements.end());
for(auto p : selements){
elements.push_back(p);
}
}
void addX(int x , piii u){
while(Sx[x].size() && Sx[x].front().F.S <= u.F.S) Sx[x].pop_front();
if(Sx[x].size() && Sx[x].front().F.F <= u.F.S){
Sx[x].front().F.F = in[adj[rinv[u.F.S]][0]];
}
while(Sx[x].size() && Sx[x].front().S == u.S){
u.F.S = Sx[x].front().F.S;
Sx[x].pop_front();
}
Sx[x].push_front(u);
}
set<int> compress;
map<int,int> poscompress;
int vc = 0;
int bit[N + 100];
int get(int x){
int s = 0;
for(int i = x ; i > 0 ; i-=(i&-i)) s+= bit[i];
return s;
}
void add(int x , int vl){
for(int i = x ; i < N + 100 ; i+=(i&-i)) bit[i] += vl;
}
int32_t main(){
scanf("%d" , &n);
for(int i = 1 ; i <= n; i++) scanf("%d" ,&C[i]) , compress.insert(C[i]);
for(auto p : compress){
poscompress[p] = ++vc;
}
for(int i = 1 ; i <= n; i ++) C[i] = poscompress[C[i]];
for(int i = 1 ; i < n ; i ++){
int x, y;
scanf("%d%d" , &x , &y);
adj[x].pb(y);
adj[y].pb(x);
edge.push_back(pii(x,y));
}
dfs(1,1);
dfs_hld(1,1);
addX(ch[1] , piii(pii(in[1] , in[1]) , C[1]));
for(auto p : edge){
elements.clear();
int X = p.F;
while(X != -1){
getX(X);
X = pai[ch[X]];
}
X = p.S;
while(X != -1){
addX(ch[X] , piii(pii(in[ch[X]] , in[X]), C[p.S]));
X = pai[ch[X]];
}
reverse(elements.begin() , elements.end());
long long ans = 0;
for(auto p : elements){
add(p.F, p.S);
long long U = get(N + 90) - get(p.F);
U *= (1LL)*((long long)p.S);
ans += U;
}
for(auto p : elements){
add(p.F , -p.S);
}
printf("%lld\n" , ans);
}
}
