#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;
const int inf = 1e9 + 5;
struct intervalac
{
int n;
vector<int> st;
void init(int N) { n = N, st.assign(2 * n, 0); }
void upd(int i, int x) { for (i += n; i > 0; i >>= 1) st[i] += x; }
ll query(int l, int r)
{
int ans = 0;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
{
if (l & 1) ans += st[l++];
if (r & 1) ans += st[--r];
}
return ans;
}
};
int n;
int cnt = 0;
vector<set<pair<pair<int, int>, int> > > zac; // zaciatky usekov v retaziach
vector<int> r, s, h, p, d, a, b, c; // moja retaz, moja velkost, najvyssi v mojej retazi, moj otec
vector<vector<int> > g;
void dfss(int u)
{
s[u] = 1;
for (int v : g[u]) d[v] = d[u] + 1, dfss(v), s[u] += s[v];
}
void dfs(int u)
{
if (r[u] == -1) h[cnt] = u, r[u] = cnt++;
int v2 = -1;
for (int v : g[u]) if (v2 == -1 || s[v] > s[v2]) v2 = v;
if (v2 != -1) r[v2] = r[u];
else zac[r[u]].insert({ {d[h[r[u]]], d[u]}, c[n] });
for (int v : g[u]) dfs(v);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
zac.assign(n, {}), r.assign(n, -1), s.assign(n, -1), h.assign(n, -1), p.assign(n, 0), d.assign(n, 0), a.assign(n - 1, 0), b.assign(n - 1, 0), c.assign(n, 0), g.assign(n, {});
for (int i = 0; i < n; i++) cin >> c[i];
c.push_back(inf);
vector<int> c2 = c;
sort(c2.begin(), c2.end());
for (int i = 0; i <= n; i++) c[i] = lower_bound(c2.begin(), c2.end(), c[i]) - c2.begin();
for (int i = 0; i < n - 1; i++) cin >> a[i] >> b[i], g[--a[i]].push_back(--b[i]), p[b[i]] = a[i];
dfss(0);
dfs(0);
intervalac in;
in.init(n + 1);
for (int i = 0; i < n - 1; i++)
{
ll ans = 0;
int u = b[i];
vector<int> reset;
while (true)
{
auto it = zac[r[u]].lower_bound({ {d[u] + 1, -1}, -1 });
if (it == zac[r[u]].begin()) // uz sme vyhodili vsetky
{
zac[r[u]].insert({ {d[h[r[u]]], d[u]}, c[b[i]] });
if (h[r[u]])
{
u = p[h[r[u]]];
continue;
}
else break;
continue;
}
it--;
int dl = it->first.first, dr = it->first.second, col = it->second;
reset.push_back(col);
zac[r[u]].erase(it);
ans += min(dr - dl + 1, d[u] - dl + 1) * 1ll * in.query(0, col - 1);
in.upd(col, min(dr - dl + 1, d[u] - dl + 1));
if (d[u] < dr) zac[r[u]].insert({ {d[u] + 1, dr}, col });
}
for (int j : reset) in.upd(j, -in.st[n + 1 + j]);
cout << ans << "\n";
}
return 0;
}
