#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define g4(a) get<4>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
using iiiii = tuple<int, int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
int N, idx, u[100005], v[100005], C[100005], par[100005], sz[100005], hv[100005], pos[100005], rev[100005], ft[100005];
vector<int> disc, adj[100005];
vector<iii> segs;
stack<int> rb;
int ls(int x) {
return x & -x;
}
void reset() {
while (!rb.empty()) {
int x = rb.top();
ft[x] = 0;
rb.pop();
}
}
void upd(int p, int v) {
for (; p <= N; p += ls(p)) {
rb.push(p);
ft[p] += v;
}
}
int qry(int p) {
int r = 0;
for (; p; p -= ls(p)) r += ft[p];
return r;
}
struct node {
node *left, *right;
int S, E, mxval, mival, pv;
bool ip;
node(int _s, int _e) : S(_s), E(_e), ip(0) {
if (S == E) {
mxval = mival = C[rev[S]];
return;
}
int M = (S + E) >> 1;
left = new node(S, M);
right = new node(M + 1, E);
mxval = max(left->mxval, right->mxval);
mival = min(left->mival, right->mival);
}
void prop() {
if (S == E || !ip) return;
left->mxval = left->mival = left->pv = right->mxval = right->mival = right->pv = pv;
left->ip = right->ip = 1;
ip = 0;
}
void get_seg(int l, int r) {
if (l > E || r < S) return;
if (l <= S && E <= r && mxval == mival) {
segs.eb(S, E, mxval);
return;
}
prop();
left->get_seg(l, r);
right->get_seg(l, r);
}
void set(int l, int r, int v) {
if (l > E || r < S) return;
if (l <= S && E <= r) {
mxval = mival = pv = v;
ip = 1;
return;
}
prop();
left->set(l, r, v);
right->set(l, r, v);
mxval = max(left->mxval, right->mxval);
mival = min(left->mival, right->mival);
}
} *root;
int get_sz(int n) {
sz[n] = 1;
for (auto u : adj[n]) {
sz[n] += get_sz(u);
}
return sz[n];
}
void dfs(int n) {
pos[n] = ++idx;
rev[pos[n]] = n;
int cur_mx = -1;
for (int i = 0; i < (int)adj[n].size(); i++) {
if (sz[adj[n][i]] > cur_mx) {
cur_mx = sz[adj[n][i]];
swap(adj[n][0], adj[n][i]);
}
}
for (int i = 0; i < (int)adj[n].size(); i++) {
if (i == 0) {
hv[adj[n][i]] = hv[n];
} else {
hv[adj[n][i]] = adj[n][i];
}
dfs(adj[n][i]);
}
}
main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> C[i];
disc.pb(C[i]);
}
sort(disc.begin(), disc.end());
for (int i = 1; i <= N; i++) {
C[i] = lower_bound(disc.begin(), disc.end(), C[i]) - disc.begin() + 1;
}
for (int i = 1; i < N; i++) {
cin >> u[i] >> v[i];
par[v[i]] = u[i];
adj[u[i]].pb(v[i]);
}
get_sz(1);
hv[1] = 1;
dfs(1);
root = new node(1, N);
for (int i = 1; i < N; i++) {
segs.clear();
for (int x = u[i]; x; x = par[hv[x]]) {
root->get_seg(pos[hv[x]], pos[x]);
root->set(pos[hv[x]], pos[x], C[v[i]]);
}
int cur = 0;
sort(segs.begin(), segs.end());
reset();
for (auto [l, r, val] : segs) {
cur += qry(N - val) * (r - l + 1);
upd(N - val + 1, r - l + 1);
}
cout << cur << '\n';
}
}
