#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <limits>
#include <set>
#include <algorithm>
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
class HLD {
public:
void init(int n) {
// this doesn't delete edges!
sz.resize(n);
in.resize(n);
out.resize(n);
rin.resize(n);
p.resize(n);
edges.resize(n);
nxt.resize(n);
h.resize(n);
}
void addEdge(int u, int v) {
edges[u].push_back(v);
edges[v].push_back(u);
}
void setRoot(int n) {
t = 0;
p[n] = n;
h[n] = 0;
prep(n, n);
nxt[n] = n;
hld(n);
}
int getLCA(int u, int v) {
while(!inSubtree(nxt[u], v)) {
u = p[nxt[u]];
}
while(!inSubtree(nxt[v], u)) {
v = p[nxt[v]];
}
return in[u] < in[v] ? u : v;
}
bool inSubtree(int u, int v) {
// is v in the subtree of u?
return in[u] <= in[v] && in[v] < out[u];
}
std::vector<std::pair<int, int>> getPathtoAncestor(int u, int anc) {
// returns ranges [l, r) that the path has
std::vector<std::pair<int, int>> ans;
//assert(inSubtree(anc, u));
while(nxt[u] != nxt[anc]) {
ans.emplace_back(in[nxt[u]], in[u] + 1);
u = p[nxt[u]];
}
// this includes the ancestor!
ans.emplace_back(in[anc], in[u] + 1);
return ans;
}
private:
std::vector<int> in, out, p, rin, sz, nxt, h;
std::vector<std::vector<int>> edges;
int t;
void prep(int on, int par) {
sz[on] = 1;
p[on] = par;
for(int i = 0; i < (int) edges[on].size(); i++) {
int &u = edges[on][i];
if(u == par) {
std::swap(u, edges[on].back());
edges[on].pop_back();
i--;
} else {
h[u] = 1 + h[on];
prep(u, on);
sz[on] += sz[u];
if(sz[u] > sz[edges[on][0]]) {
std::swap(edges[on][0], u);
}
}
}
}
void hld(int on) {
in[on] = t++;
rin[in[on]] = on;
for(auto u : edges[on]) {
nxt[u] = (u == edges[on][0] ? nxt[on] : u);
hld(u);
}
out[on] = t;
}
};
template <class Info = int>
class ColorUpdate {
public:
struct Range {
Range(int ll = 0) { this->l = ll; }
Range(int ll, int rr, Info vv) {
l = ll;
r = rr;
v = vv;
}
int l, r;
Info v;
bool operator < (const Range &b) const { return l < b.l; }
};
std::vector<Range> upd(int l, int r, Info v) {
std::vector<Range> ans;
if(l >= r) return ans;
auto it = ranges.lower_bound(l);
if(it != ranges.begin()) {
it--;
if(it->r > l) {
auto cur = *it;
ranges.erase(it);
ranges.insert(Range(cur.l, l, cur.v));
ranges.insert(Range(l, cur.r, cur.v));
}
}
it = ranges.lower_bound(r);
if(it != ranges.begin()) {
it--;
if(it->r > r) {
auto cur = *it;
ranges.erase(it);
ranges.insert(Range(cur.l, r, cur.v));
ranges.insert(Range(r, cur.r, cur.v));
}
}
for(it = ranges.lower_bound(l); it != ranges.end() && it->l < r; it++) {
ans.push_back(*it);
}
ranges.erase(ranges.lower_bound(l), ranges.lower_bound(r));
ranges.insert(Range(l, r, v));
return ans;
}
private:
std::set<Range> ranges;
};
template <class T>
class FenwickTree {
public:
void init(int s) {
n = s;
bit.assign(n + 1, 0);
}
void init(const std::vector<T> &a) {
n = a.size();
bit.assign(n + 1, 0);
for(int i = 1; i <= n; i++) {
bit[i] += a[i - 1];
if(i + (i & -i) <= n) {
bit[i + (i & -i)] += bit[i];
}
}
}
T qry(int x) {
x = std::min(x, (int)bit.size() - 1);
T ans = 0;
for(; x > 0; x -= x & -x) {
ans += bit[x];
}
return ans;
}
void upd(int x, T v) {
x = std::max(x, 1);
for(; x <= n; x += x & -x) {
bit[x] += v;
}
}
private:
int n;
std::vector<T> bit;
};
int main() {
std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
int n;
std::cin >> n;
std::vector<int> c(n);
for(int i = 0; i < n; i++) {
std::cin >> c[i];
}
auto vals = c;
std::sort(vals.begin(), vals.end());
for(auto &v : c) {
v = std::upper_bound(vals.begin(), vals.end(), v) - vals.begin();
}
std::vector<std::pair<int, int>> edges;
HLD tree;
tree.init(n);
for(int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
u--;v--;
edges.emplace_back(u, v);
tree.addEdge(u, v);
}
tree.setRoot(0);
ColorUpdate<int> colors;
FenwickTree<int> fw;
fw.init(n);
for(auto e : edges) {
auto path = tree.getPathtoAncestor(e.second, 0);
std::vector<std::pair<int, int>> arr;
for(auto chain : path) {
auto col = colors.upd(chain.first, chain.second, c[e.second]);
std::reverse(col.begin(), col.end());
for(auto elem : col) {
arr.emplace_back(elem.v, elem.r - elem.l);
}
}
long long ans = 0;
for(auto elem : arr) {
//std::cout << "got " << elem.first << " with freq " << elem.second << std::endl;
fw.upd(elem.first, elem.second);
ans += (long long) fw.qry(elem.first - 1) * elem.second;
}
for(auto elem : arr) {
fw.upd(elem.first, -elem.second);
}
std::cout << ans << '\n';
}
}
