# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 2;
int n, c[N], a[N], b[N], h[N], fen[N];
int p[18][N], tin[N], tout[N], timer;
pair <int, int> t[N * 4];
vector <int> vec, g[N];
void dfs(int v, int pr = 0){
tin[v] = ++ timer;
p[0][v] = pr;
for(int i = 1; i <= 17; i ++)
p[i][v] = p[i - 1][p[i - 1][v]];
for(int to : g[v]){
if(to == pr) continue;
h[to] = h[v] + 1;
dfs(to, v);
}
tout[v] = timer;
}
bool upper(int a, int b){
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b){
if(upper(a, b)) return a;
if(upper(b, a)) return b;
for(int i = 17; i >= 0; i --)
if(p[i][a] && !upper(p[i][a], b))
a = p[i][a];
return p[0][a];
}
void update(int pos, int val, int vv, int v = 1, int tl = 1, int tr = n){
if(tl == tr)
t[v] = {val, vv};
else {
int tm = (tl + tr) >> 1;
if(pos <= tm)
update(pos, val, vv, v << 1, tl, tm);
else
update(pos, val, vv, (v << 1) | 1, tm + 1, tr);
t[v] = max(t[v << 1], t[(v << 1) | 1]);
}
}
pair <int, int> get(int l, int r, int v = 1, int tl = 1, int tr = n){
if(l > tr || tl > r) return {0, 0};
if(l <= tl && tr <= r) return t[v];
int tm = (tl + tr) >> 1;
return max(get(l, r, v << 1, tl, tm),
get(l, r, (v << 1) | 1, tm + 1, tr));
}
void Update(int r, int val){
for(; r > 0; r = (r & (r + 1)) - 1)
fen[r] += val;
}
int Get(int pos){
int res = 0;
for(; pos <= n + 1; pos |= pos + 1)
res += fen[pos];
return res;
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i ++){
scanf("%d", &c[i]);
vec.emplace_back(c[i]);
}
sort(vec.begin(), vec.end());
vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
for(int i = 1; i <= n; i ++)
c[i] = lower_bound(vec.begin(), vec.end(), c[i]) - vec.begin() + 1;
for(int i = 1; i < n; i ++){
scanf("%d %d", &a[i], &b[i]);
g[a[i]].emplace_back(b[i]);
g[b[i]].emplace_back(a[i]);
}
h[1] = 1;
dfs(1);
for(int i = 1; i < n; i ++){
int v = 1, prelca = 0;
vector < pair <int, int> > vc;
while(1){
pair <int, int> mx = get(tin[v], tout[v]);
int LCA = lca(mx.second, a[i]);
vc.push_back({h[LCA] - h[prelca], c[mx.second]});
// if(i == 7){
// cout << mx.second << " " << a[i] << " " << LCA << endl;
// }
prelca = LCA;
if(v == a[i]) break;
int vv = a[i];
for(int i = 17; i >= 0; i --){
if(p[i][vv] && !upper(p[i][vv], LCA))
vv = p[i][vv];
}
v = vv;
}
long long ans = 0;
for(int j = 0; j < vc.size(); j ++){
int f = vc[j].first, s = vc[j].second;
ans += Get(s + 1) * f;
Update(s, f);
}
printf("%I64d\n", ans);
update(tin[b[i]], i, b[i]);
for(int j = 0; j < vc.size(); j ++){
int f = vc[j].first, s = vc[j].second;
Update(s, -f);
}
}
}
