#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define Debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long LL;
typedef long double LD;
typedef unsigned int uint;
typedef pair <int, int> pii;
typedef unsigned long long uLL;
template <typename T> inline void Read(T &x) {
char c = getchar();
bool f = false;
for (x = 0; !isdigit(c); c = getchar()) {
if (c == '-') {
f = true;
}
}
for (; isdigit(c); c = getchar()) {
x = x * 10 + c - '0';
}
if (f) {
x = -x;
}
}
template <typename T> inline bool CheckMax(T &a, const T &b) {
return a < b ? a = b, true : false;
}
template <typename T> inline bool CheckMin(T &a, const T &b) {
return a > b ? a = b, true : false;
}
const int N = 100005;
int n, top, c[N], d[N], f[N], siz[N], sta[N], val[N], chd[N][2];
vector <pii> seq;
LL ans, b[N];
inline bool IsRoot(int x) {
return chd[f[x]][0] != x && chd[f[x]][1] != x;
}
inline void AddTag(int x, int y) {
val[x] = c[x] = y;
}
inline void PushUp(int x) {
siz[x] = siz[chd[x][0]] + siz[chd[x][1]] + 1;
}
inline void PushDown(int x) {
if (val[x]) {
AddTag(chd[x][0], val[x]), AddTag(chd[x][1], val[x]), val[x] = 0;
}
}
inline void Rotate(int x) {
int y = f[x], z = f[y], k = chd[y][1] == x;
if (!IsRoot(y)) {
chd[z][chd[z][1] == y] = x;
}
f[chd[y][k] = chd[x][!k]] = y;
f[f[chd[x][!k] = y] = x] = z;
PushUp(y), PushUp(x);
}
inline void Splay(int x) {
sta[top = 1] = x;
for (int i = x; !IsRoot(i); sta[++top] = i = f[i]);
for (; top; PushDown(sta[top--]));
for (int y = f[x], z = f[y]; !IsRoot(x); Rotate(x), y = f[x], z = f[y]) {
if (!IsRoot(y)) {
Rotate((chd[y][1] == x) == (chd[z][1] == y) ? y : x);
}
}
}
inline void Access(int x) {
for (int t = 0; x; x = f[x]) {
Splay(x), chd[x][1] = t, t = x, PushUp(x), seq.pb(mp(c[x], siz[x]));
}
}
inline void Modify(int x, int y) {
for (; x <= n; x += x & -x) {
b[x] += y;
}
}
inline LL Query(int x) {
LL r = 0;
for (; x; x -= x & -x) {
r += b[x];
}
return r;
}
inline void Solve() {
ans = 0;
for (int i = seq.size() - 1; i; --i) {
seq[i].Y -= seq[i - 1].Y;
}
for (int i = 0; i < seq.size(); ++i) {
ans += 1LL * seq[i].Y * Query(seq[i].X - 1);
Modify(seq[i].X, seq[i].Y);
}
printf("%lld\n", ans);
for (int i = 0; i < seq.size(); ++i) {
Modify(seq[i].X, -seq[i].Y);
}
seq.clear();
}
int main() {
#ifdef wxh010910
freopen("d.in", "r", stdin);
#endif
Read(n);
for (int i = 1; i <= n; ++i) {
Read(c[i]), d[i] = c[i], siz[i] = 1;
}
sort(d + 1, d + n + 1);
for (int i = 1; i <= n; ++i) {
c[i] = lower_bound(d + 1, d + n + 1, c[i]) - d;
}
for (int i = 1, x, y; i < n; ++i) {
Read(x), Read(y);
Access(x), Splay(x);
AddTag(x, c[y]), f[y] = x, Solve();
}
#ifdef wxh010910
Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
return 0;
}
