/*
Author: Nguyen Chi Thanh - High School for the Gifted - VNU.HCM (i2528)
*/
#include <bits/stdc++.h>
using namespace std;
/* START OF TEMPALTE */
// #define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define popcount __builtin_popcountll
#define all(x) (x).begin(), (x).end()
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(x) (1ll << (x))
#define SZ(a) ((int32_t)a.size())
#define debug(a, l, r) {for (int _i = (l); _i <= (r); ++_i) cout << (a)[_i] << ' '; cout << '\n';}
template<class X, class Y>
bool minimize(X &x, const Y &y) {
if (x > y) {
x = y;
return true;
} else return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
if (x < y) {
x = y;
return true;
} else return false;
}
/* END OF TEMPALTE */
struct HeavyLightDecomposition {
int n, curpos, curchain;
vector<vector<int>> adj;
vector<int> sz, parent, head, chain, pos;
void dfs(int u, int par = 0) {
sz[u] = 1; parent[u] = par;
for (int v : adj[u]) {
if (v == par) continue;
dfs(v, u);
sz[u] += sz[v];
}
}
void hld(int u, int par = 0) {
if (!head[curchain]) head[curchain] = u;
chain[u] = curchain; pos[u] = curpos;
++curpos;
int nxt = 0;
for (int v : adj[u])
if (v != par && (nxt == 0 || sz[v] > sz[nxt]))
nxt = v;
if (nxt) hld(nxt, u);
for (int v : adj[u]) if (v != par && v != nxt) {
++curchain;
hld(v, u);
}
}
void build() {
curpos = 1; curchain = 1;
dfs(1); hld(1);
}
vector<pii> query(int u, int v) {
vector<pii> res;
while (chain[u] != chain[v]) {
if (chain[u] > chain[v]) {
res.push_back({pos[head[chain[u]]], pos[u]});
u = parent[head[chain[u]]];
} else {
res.push_back({pos[head[chain[v]]], pos[v]});
v = parent[head[chain[v]]];
}
}
if (sz[u] > sz[v]) res.push_back({pos[u], pos[v]});
else res.push_back({pos[v], pos[u]});
return res;
}
void add_edge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
HeavyLightDecomposition() {}
void init(int _n) {*this = HeavyLightDecomposition(_n);}
HeavyLightDecomposition (int _n) : n(_n), adj(n + 5),
sz(n + 5), parent(n + 5), head(n + 5), chain(n + 5),
pos(n + 5) {}
};
struct Range {
int l, r, x;
bool operator < (const Range &other) const {
if (l == other.l && r == other.r) return x < other.x;
if (l == other.l) return r < other.r;
return l < other.l;
}
};
struct RangeContainer{
set<Range> st;
RangeContainer () {
st.clear();
}
void add(Range x) {
st.insert(x);
}
void del(Range x) {
st.erase(st.find(x));
}
bool intersect(Range x, Range y) {
int a = x.l, b = x.r;
int c = y.l, d = y.r;
if (a > d || b < c) return 0;
return 1;
}
void get(int L, int R, vector<Range> &res) {
if (st.empty() || L > R) return;
auto it = st.upper_bound({L, (int)2e9, (int)2e9});
if (it != st.begin()) --it;
for (; it != st.end(); ++it) {
if (it->l > R) break;
if (!intersect(*it, {L, R, 0})) continue;
res.push_back({max(L, it->l), min(R, it->r), it->x});
}
}
void rangeSet(int L, int R, int x) {
vector<Range> added, deleted;
auto it = st.upper_bound({L, (int)2e9, (int)2e9});
if (it != st.begin()) --it;
for (; it != st.end(); ++it) {
Range tmp = *it;
if (tmp.l > R) break;
if (intersect(tmp, {L, R, x})) {
int l = tmp.l, r = tmp.r, val = tmp.x;
if (l < L) added.push_back({l, L - 1, val});
if (R < r) added.push_back({R + 1, r, val});
deleted.push_back(tmp);
}
}
added.push_back({L, R, x});
for (auto x : deleted) del(x);
sort(all(added));
vector<Range> merged;
for (auto cur : added) {
if (merged.empty()) merged.push_back(cur);
else {
Range &last = merged.back();
if (last.r + 1 == cur.l && last.x == cur.x) {
last.r = cur.r;
} else {
merged.push_back(cur);
}
}
}
auto jt = st.lower_bound({L, -1, -1});
if (jt != st.begin()) {
auto prv = prev(jt);
if (prv->r + 1 == merged[0].l && prv->x == merged[0].x) {
Range tmp = *prv;
del(tmp);
merged[0].l = tmp.l;
}
}
jt = st.lower_bound({R + 1, -1, -1});
if (jt != st.end()) {
if (merged.back().r + 1 == jt->l && merged.back().x == jt->x) {
Range tmp = *jt;
del(tmp);
merged.back().r = tmp.r;
}
}
for (auto x : merged) add(x);
}
};
struct FenwickTree {
int n;
vector<ll> fen;
void init(int _n) {
n = _n;
fen.resize(n + 5, 0);
}
void update(int idx, ll v) {
for (int i = idx; i <= n; i += i & -i)
fen[i] += v;
}
ll get(int idx) {
ll res = 0;
for (int i = idx; i; i -= i & -i)
res += fen[i];
return res;
}
};
const int MAXN = 1e5 + 5;
int n, c[MAXN];
pii queries[MAXN];
HeavyLightDecomposition HLD;
RangeContainer ds;
FenwickTree BIT;
void init() {
cin >> n; HLD.init(n);
vector<int> vals;
for (int i = 1; i <= n; ++i) {
cin >> c[i];
vals.push_back(c[i]);
}
for (int i = 1; i < n; ++i) {
int a, b; cin >> a >> b;
queries[i] = {a, b};
HLD.add_edge(a, b);
}
sort(all(vals));
vals.erase(unique(all(vals)), end(vals));
for (int i = 1; i <= n; ++i) {
c[i] = lower_bound(all(vals), c[i]) - begin(vals) + 1;
}
}
void solve() {
HLD.build();
{
vector<int> val(n + 5);
for (int i = 1; i <= n; ++i)
val[HLD.pos[i]] = c[i];
ds = RangeContainer();
int i = 1;
while (i <= n) {
int j = i;
while (j < n && val[j] == val[j + 1]) ++j;
ds.add({i, j, val[i]});
i = j + 1;
}
}
vector<pii> ranges, rollback;
vector<Range> discs;
BIT.init(n);
for (int i = 1; i < n; ++i) {
int a = queries[i].fi, b = queries[i].se;
ranges = HLD.query(1, a);
reverse(all(ranges));
discs.clear(); rollback.clear();
for (auto &e : ranges)
ds.get(e.fi, e.se, discs);
ll cost = 0;
for (auto &e : discs) {
int num = e.r - e.l + 1;
int val = e.x;
cost += 1ll * num * (BIT.get(n) - BIT.get(val));
BIT.update(val, num);
rollback.push_back({val, -num});
}
cout << cost << '\n';
for (auto &e : rollback) BIT.update(e.fi, e.se);
for (auto &e : ranges)
ds.rangeSet(e.fi, e.se, c[b]);
}
}
signed main() {
#ifdef NCTHANH
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
init();
solve();
return 0;
}
