#include <bits/stdc++.h>
//#include "bits_stdc++.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i)
#define RFOR(i, x, n) for (ll i =x; i>=n; --i)
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;
ll n, hld_label = 0;
ll const MAXN = 100010;
vector<ll> adj[MAXN];
ll depth[MAXN], siz[MAXN], heavyp[MAXN], parent[MAXN], in[MAXN], out[MAXN], val[MAXN], a[MAXN], b[MAXN];
deque<pi> dq[MAXN];
void dfs_size(ll p, ll node) // hld pre-order + subtree size
{
if (adj[node].size()>=2 && adj[node][0]==p) swap(adj[node][0], adj[node][1]);
siz[node]=1;
for (auto& u: adj[node])
{
if (u==p) continue;
depth[u] = depth[node]+1;
parent[u] = node;
dfs_size(node, u);
siz[node] += siz[u];
if (siz[u]>siz[adj[node][0]]) swap(adj[node][0], u); // order heavy edge together
}
}
// heavyp = next ancester with conseutive path (as in sgtree) to current node
void dfs_hld(ll p, ll node)
{
hld_label++;
in[node] = hld_label;
dq[heavyp[node]].pb(mp(val[node], 1));
for (ll u: adj[node])
{
if (u==p) continue;
if (u==adj[node][0]) heavyp[u] = heavyp[node]; // trace the topmost vertice in the path
else heavyp[u] = u; // for light vertice, this is simply itself
dfs_hld(node, u);
}
out[node] = hld_label;
}
// BIT
vector<ll> dis;
vector<ll> fenwick(MAXN,0);
ll ps(ll i)
{
if (i==0) return 0;
ll sum=0;
while (i>0)
{
sum+=fenwick[i];
i-=i&(-i);
}
return sum;
}
void update(ll i, ll v)
{
while (i<=100005)
{
fenwick[i]+=v;
i+=i&(-i);
}
}
int main()
{
input(n);
for (ll i=1; i<=n; ++i) {input(val[i]); dis.pb(val[i]);}
discretize(dis);
for (ll i=1; i<=n; ++i) {val[i] = lb(all(dis), val[i])-dis.begin() + 1;}
for (ll i=1; i<=n-1; ++i)
{
input2(a[i], b[i]);
adj[a[i]].pb(b[i]);
}
parent[1] = -1;
depth[1] = 0;
heavyp[1] = 1;
dfs_size(-1, 1);
dfs_hld(-1, 1);
for (ll i=1; i<=n-1; ++i)
{
//show(i);
ll ans = 0;
ll now = a[i];
vector<pi> undo;
while (now!=-1)
{
//show(now);
vector<pi> qq;
ll cnt = depth[now] - depth[heavyp[now]] +1;
while (dq[heavyp[now]].size() && cnt)
{
ll take = min(dq[heavyp[now]].front().s, cnt);
//show2(dq[heavyp[now]].front().f, dq[heavyp[now]].front().s);
cnt-=take;
dq[heavyp[now]].front().s-=take;
ll idx = lb(all(dis), dq[heavyp[now]].front().f)-dis.begin() + 1;
//ans += ps(idx-1)*take;
//update(idx, take);
qq.pb(mp(idx, take));
if (dq[heavyp[now]].front().s ==0) dq[heavyp[now]].pop_front();
}
dq[heavyp[now]].push_front(mp(val[b[i]], depth[now] - depth[heavyp[now]] +1));
now = parent[heavyp[now]];
reverse(all(qq));
for (pi u: qq) ans += ps(u.f-1)*u.s, update(u.f, u.s), undo.pb(u);
}
for (pi u: undo) update(u.f, -u.s);
print(ans, '\n');
}
return 0;
}
