#include <bits/stdc++.h>
using namespace std;
const int NS = (int)1e5 + 4;
int n, c[NS];
vector<int> way[NS];
int sz[NS], in[NS], incnt, up[NS], pr[NS];
pair<int, int> que[NS];
vector<pair<int, int>> block;
void dfs_sz(int x, int from){
sz[x] = 1; in[x] = incnt++; pr[x] = from;
for(auto&nxt:way[x]){
if(nxt == from){
continue;
}
dfs_sz(nxt, x);
sz[x] += sz[nxt];
if(way[x][0] == from || sz[way[x][0]] < sz[nxt]){
swap(way[x][0], nxt);
}
}
}
void dfs_hld(int x, int from){
for(auto&nxt:way[x]){
if(way[x][0] == from){
continue;
}
if(way[x][0] == nxt){
up[nxt] = up[x];
}
else{
up[nxt] = nxt;
}
dfs_hld(nxt, x);
}
}
struct Seg{
int n;
vector<int> tree, lazy;
Seg(int N):n(N){
tree.resize(n * 4, -1), lazy.resize(n * 4, -1);
}
void add(int x, int l, int r, int val){
lazy[x] = val;
tree[x] = val;
}
void update(int x, int l, int r){
if(lazy[x] == -1) return;
int mid = (l + r) >> 1;
add(x * 2, l, mid, lazy[x]), add(x * 2 + 1, mid + 1, r, lazy[x]);
lazy[x] = -1;
}
void push(int x, int l, int r, int pl, int pr, int val){
if(pr < l || pl > r || pl > pr) return;
if(l >= pl && r <= pr){
add(x, l, r, val);
return;
}
update(x, l, r);
int mid = (l + r) >> 1;
push(x * 2, l, mid, pl, pr, val), push(x * 2 + 1, mid + 1, r, pl, pr, val);
if(tree[x * 2] == tree[x * 2 + 1] && tree[x * 2] != -1){
tree[x] = tree[x * 2];
}
else{
tree[x] = -1;
}
}
void get(int x, int l, int r, int fl, int fr){
if(fr < l || fl > r || fl > fr) return;
if(tree[x] != -1){
block.push_back({tree[x], min(r, fr) - max(l, fl) + 1});
return;
}
update(x, l, r);
int mid = (l + r) >> 1;
get(x * 2 + 1, mid + 1, r, fl, fr);
get(x * 2, l, mid, fl, fr);
}
};
struct Fenwick{
int n;
vector<int> tree;
Fenwick(int N):n(N){
tree.resize(n);
}
void push(int x, int y){
for(int i = x; i < n; i |= i + 1) tree[i] += y;
}
int get(int x){
int rv = 0;
for(int i = x; i >= 0; i = (i & (i + 1)) - 1){
rv += tree[i];
}
return rv;
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
vector<int> srt;
for(int i = 0; i < n; ++i){
cin >> c[i];
srt.push_back(c[i]);
}
sort(srt.begin(), srt.end());
srt.erase(unique(srt.begin(), srt.end()), srt.end());
for(int i = 0; i < n; ++i){
c[i] = lower_bound(srt.begin(), srt.end(), c[i]) - srt.begin();
}
for(int i = 0; i < n - 1; ++i){
int x, y; cin >> x >> y; --x, --y;
que[i] = {x, y};
way[x].push_back(y), way[y].push_back(x);
}
dfs_sz(0, -1);
dfs_hld(0, -1);
Seg seg(n + 4);
seg.push(1, 0, n - 1, 0, 0, c[0]);
Fenwick sum(n + 4);
for(int i = 0; i < n - 1; ++i){
int x = que[i].first;
while(x != -1){
if(up[x] == x){
block.push_back({c[x], 1});
x = pr[x];
}
else{
seg.get(1, 0, n - 1, in[up[x]], in[x]);
x = pr[up[x]];
}
}
vector<pair<int, int>> col;
for(auto&i:block){
if((int)col.size() && col.back().first == i.first){
col.back().second += i.second;
}
else{
col.push_back({i.first, i.second});
}
}
block.clear();
long long ans = 0;
for(auto&i:col){
ans += (long long)sum.get(i.first - 1) * i.second;
sum.push(i.first, i.second);
}
for(auto&i:col){
sum.push(i.first, -i.second);
}
cout << ans << '\n';
x = que[i].second;
while(x != -1){
if(up[x] == x){
seg.push(1, 0, n - 1, in[x], in[x], c[que[i].second]);
x = pr[x];
}
else{
seg.push(1, 0, n - 1, in[up[x]], in[x], c[que[i].second]);
x = pr[up[x]];
}
}
}
return 0;
}
