#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1 << 17;
//#define debug(...) fprintf(stderr, __VA_ARGS__)
#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
int N;
int A[MAXN], B[MAXN];
int C[MAXN];
vector<int> adj[MAXN];
int ent[MAXN], exi[MAXN];
struct segtree {
pii tree[2 * MAXN]; //pii(time, value)
void update (int x, pii v) {
debug("update %d, (%d, %d)\n", x, v.fi, v.se);
tree[x += MAXN] = v;
while (x >>= 1) {
tree[x] = max(tree[2 * x], tree[2 * x + 1]);
}
}
pii query (int a, int b, int cur = 1, int lt = 0, int rt = MAXN) {
if (rt <= a || b <= lt) {
return pii(-1, -1);
}
if (a <= lt && rt <= b) {
return tree[cur];
}
int mid = (lt + rt) / 2;
return max(query(a, b, 2 * cur, lt, mid), query(a, b, 2 * cur + 1, mid, rt));
}
} seg;
void updpath (int x) {
static int updtime = 0;
seg.update(ent[x], pii(++updtime, C[x]));
}
int lastupd (int x) {
//last update of this one
//debug("x = %d. query [%d, %d)\n", x, ent[x], exi[x]);
return seg.query(ent[x], exi[x]).se;
}
void dfs (int x) {
static int cur = 0;
ent[x] = cur++;
for (int y : adj[x]) {
dfs(y);
}
//debug("updpath(%d)\n", x);
exi[x] = cur;
updpath(x);
assert(lastupd(x) == C[x]);
}
struct node {
node *ch[2], *p;
int id;
int size;
} *null = new node, nodes[MAXN];
int getdir (node *n) {
if (n->p == null) {
return -1;
}
for (int i = 0; i < 2; i++) {
if (n == n->p->ch[i]) {
return i;
}
}
return -1;
}
bool isroot (node *n) {
return getdir(n) == -1;
}
void setc (node *n, node *c, int d) {
n->ch[d] = c;
if (c != null) {
c->p = n;
}
}
void push (node *n) {
//nothing
}
void pull (node *n) {
n->size = n->ch[0]->size + 1 + n->ch[1]->size;
}
void rot (node *n) {
node *p = n->p, *g = p->p;
bool d = getdir(n);
//note that this matters in an LCT. cannot cal setc on g and n
if (!isroot(p)) {
g->ch[getdir(p)] = n;
}
setc(p, n->ch[!d], d);
n->p = g; //this line forgot include...
#warning is this correct (in rot function)?
setc(n, p, !d);
pull(p);
pull(n);
}
void splay (node *n) {
while (!isroot(n)) {
node *p = n->p;
if (!isroot(p)) {
push(p->p);
}
push(p);
push(n);
if (!isroot(p)) {
rot(getdir(n) == getdir(p) ? n : p);
}
rot(n);
}
push(n);
}
vector<pii> expose (node *u) {
//pii(size, value of node)
debug("----------------expose %d-------------------\n", u->id);
vector<pii> res;
int psize = 0;
for (node *cur = u, *v = null; cur != null; v = cur, cur = cur->p) {
splay(cur);
assert(v == null || v->p == cur);
cur->ch[1] = v;
pull(cur);
debug("id = %d, lastupd = %d. Size = %d\n", cur->id, lastupd(cur->id), cur->size - psize);
if (v != null) {
res.push_back(pii(lastupd(cur->id), cur->size - psize));
}
psize = cur->size;
}
splay(u);
/*
for (pii p : res) {
debug("(%d, %d) ", p.fi, p.se);
}
debug("\n");
*/
return res;
}
struct fenwick {
ll bit[MAXN];
void update (int x, ll v) {
for (x++; x < MAXN; x += (x & -x)) {
bit[x] += v;
}
}
ll query (int x) {
ll res = 0;
for (x++; x; x &= (x - 1)) {
res += bit[x];
}
return res;
}
} fen;
int main() {
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d", &C[i]);
}
//compress C
vector<int> vals(C, C + N);
sort(all(vals));
vals.resize(unique(all(vals)) - vals.begin());
for (int i = 0; i < N; i++) {
C[i] = lower_bound(all(vals), C[i]) - vals.begin();
debug("C[%d] = %d\n", i, C[i]);
}
for (int i = 0; i < N - 1; i++) {
scanf("%d %d", &A[i], &B[i]);
A[i]--;
B[i]--;
adj[A[i]].push_back(B[i]);
}
dfs(0);
//NOW THE NODES!
null->ch[0] = null->ch[1] = null->p = null;
null->id = -1073741819;
null->size = 0;
for (int i = 0; i < N; i++) {
nodes[i].ch[0] = nodes[i].ch[1] = nodes[i].p = null;
nodes[i].id = i;
nodes[i].size = 1;
}
for (int i = 0; i < N - 1; i++) {
nodes[B[i]].p = nodes + A[i];
}
for (int i = 0; i < N - 1; i++) {
int a = A[i], b = B[i];
vector<pii> v = expose(nodes + b);
//we want the number of strictly less than this value.
debug("--------SATAN 1-------------\n");
ll ans = 0;
for (pii p : v) {
debug("(%d, %d)...\n", p.fi, p.se);
debug("query(%d) = %lld\n", p.fi - 1, fen.query(p.fi - 1));
ans += p.se * fen.query(p.fi - 1);
debug("update(%d, %d)\n", p.fi, p.se);
fen.update(p.fi, p.se);
}
for (pii p : v) {
fen.update(p.fi, -p.se);
}
printf("%lld\n", ans);
updpath(b);
debug("--------SATAN 2-------------\n");
}
}
