#include <bits/stdc++.h>
#define int long long
using namespace std;
template <class T> class Fenwick {
public:
int lim;
vector<T> bit;
Fenwick(int n) : lim(n + 1), bit(lim) {}
void upd(int pos, T val) {
for (pos++; pos < lim; pos += pos & -pos)
bit[pos] += val;
}
T sum(int r) { // < r
T ret = 0;
for (; r; r -= r & -r)
ret += bit[r];
return ret;
}
T sum(int l, int r) { // [l, r)
return sum(r) - sum(l);
}
};
const int MAXN = 1e5;
vector<int> adj[MAXN];
int par[MAXN], root[MAXN], sz[MAXN], depth[MAXN], heavy[MAXN];
map<pair<int, int>, int> segs[MAXN];
int nbSommets;
Fenwick<int> fen(MAXN);
void dfs(int u) {
sz[u] = 1;
for (int v : adj[u]) {
depth[v] = depth[u] + 1;
dfs(v);
sz[u] += sz[v];
}
heavy[u] = -1;
for (int v : adj[u])
if (2 * sz[v] >= sz[u])
heavy[u] = v;
}
void dfs2(int u) {
for (int v : adj[u]) {
if (heavy[u] == v)
root[v] = root[u];
else
root[v] = v;
dfs2(v);
}
}
int query(int iNoeud) { // Go up from iNoeud !
vector<pair<int, int>> toErase;
int ret = 0;
auto pushChange = [&]() {
auto it = segs[root[iNoeud]].upper_bound(make_pair(depth[iNoeud], 1e18));
while (it != segs[root[iNoeud]].begin()) {
it--;
auto [deb, fin] = it->first;
int val = it->second;
int cb = min(depth[iNoeud], fin) - deb + 1;
ret += cb * fen.sum(val);
fen.upd(val, cb);
toErase.emplace_back(val, cb);
}
};
while (root[iNoeud]) {
pushChange();
iNoeud = par[root[iNoeud]];
}
pushChange();
for (auto [val, cb] : toErase)
fen.upd(val, -cb);
return ret;
}
void upd(int iNoeud, int val) { // change all values above iNoeud !
auto pullChange = [&]() {
while (!segs[root[iNoeud]].empty() and
segs[root[iNoeud]].begin()->first.second <= depth[iNoeud])
segs[root[iNoeud]].erase(segs[root[iNoeud]].begin());
if (!segs[root[iNoeud]].empty() and
depth[iNoeud] < segs[root[iNoeud]].begin()->first.second) {
auto [deb, fin] = segs[root[iNoeud]].begin()->first;
auto v = segs[root[iNoeud]].begin()->second;
segs[root[iNoeud]].erase(segs[root[iNoeud]].begin());
segs[root[iNoeud]][make_pair(depth[iNoeud] + 1, fin)] = v;
}
segs[root[iNoeud]][make_pair(depth[root[iNoeud]], depth[iNoeud])] = val;
};
while (root[iNoeud]) {
pullChange();
iNoeud = par[root[iNoeud]];
}
pullChange();
}
signed main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> nbSommets;
vector<int> distinct(nbSommets);
vector<int> liveliness(nbSommets);
for (int i = 0; i < nbSommets; ++i) {
cin >> liveliness[i];
distinct[i] = liveliness[i];
}
sort(distinct.begin(), distinct.end());
distinct.resize(unique(distinct.begin(), distinct.end()) - distinct.begin());
for (int i = 0; i < nbSommets; ++i)
liveliness[i] =
lower_bound(distinct.begin(), distinct.end(), liveliness[i]) -
distinct.begin();
vector<pair<int, int>> edges(nbSommets - 1);
for (auto &[A, B] : edges) {
cin >> A >> B;
--A, --B;
par[B] = A;
adj[A].push_back(B);
}
dfs(0);
dfs2(0);
segs[0][{0, 0}] = liveliness[0];
for (auto [a, b] : edges) {
cout << query(a) << '\n';
upd(b, liveliness[b]);
/*cout << "==============" << endl;
for (int i = 0; i < nbSommets; ++i)
if (i == root[i]) {
cout << i + 1 << ": ";
for (auto it : segs[i])
cout << it.first.first << ' ' << it.first.second << " = "
<< it.second + 1 << ' ';
cout << endl;
}*/
}
}
