#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;
const int N = 100005, L = 131072, G = 17, inf = 1e9;
int n, x[N], a[N], b[N];
int sp[N][G], dep[N], s[N], e[N], cc;
vector<int> adj[N], cpr;
vector<pii> act;
struct maxseg {
int v[4*N];
void upd (int P, int V) {
P += L;
while(P) {
v[P] = max(v[P], V);
P /= 2;
}
}
int get (int S, int E) {
S += L;
E += L;
int R = 0;
while(S <= E) {
if(S%2 == 1) R = max(R, v[S++]);
if(E%2 == 0) R = max(R, v[E--]);
S /= 2;
E /= 2;
}
return R;
}
int lb (int S, int V) {
S += L;
while(true) {
if(v[S] > V) break;
S = (S - 1) / 2;
}
while(S < L) {
S = 2*S + (v[2*S+1] > V);
}
return S - L;
}
int rb (int S, int V) {
S += L;
while(true) {
if(v[S] > V) break;
S = (S + 1) / 2;
}
while(S < L) {
S = 2*S+1 - (v[2*S] > V);
}
return S - L;
}
} ms;
struct sumseg {
int v[4*N];
void upd (int P, int V) {
P += L;
while(P) {
v[P] += V;
P /= 2;
}
}
int get (int S, int E) {
S += L;
E += L;
int R = 0;
while(S <= E) {
if(S%2 == 1) R += v[S++];
if(E%2 == 0) R += v[E--];
S /= 2;
E /= 2;
}
return R;
}
} ss;
void calc (int I) {
s[I] = ++cc;
for(auto &T : adj[I]) {
sp[T][0] = I;
dep[T] = dep[I] + 1;
calc(T);
}
e[I] = cc;
}
int main()
{
scanf("%d",&n);
ms.upd(0, inf);
ms.upd(n+1, inf);
for(int i=1;i<=n;i++) {
scanf("%d",&x[i]);
cpr.push_back(x[i]);
}
sort(cpr.begin(), cpr.end());
cpr.erase(unique(cpr.begin(), cpr.end()), cpr.end());
for(int i=1;i<=n;i++) {
x[i] = lower_bound(cpr.begin(), cpr.end(), x[i]) - cpr.begin();
}
b[0] = 1;
for(int i=1;i<n;i++) {
scanf("%d%d",&a[i],&b[i]);
adj[a[i]].push_back(b[i]);
}
dep[1] = 1;
calc(1);
for(int i=1;i<G;i++) {
for(int j=1;j<=n;j++) {
sp[j][i] = sp[sp[j][i-1]][i-1];
}
}
for(int i=1;i<n;i++) {
long long ans = 0;
for(int C = a[i], T; C; C = T) {
int V = ms.get(s[C], e[C]);
int S = ms.lb(s[C], V) + 1;
int E = ms.rb(e[C], V) - 1;
T = C;
for(int j=G;j--;) {
int P = sp[T][j];
if(S <= s[P] && e[P] <= E) T = P;
}
T = sp[T][0];
int A = x[b[V]], B = dep[C] - dep[T];
ans += 1ll * B * ss.get(0, A-1);
ss.upd(A, B);
act.push_back({A, B});
}
printf("%lld\n",ans);
for(auto &T : act) {
int A, B;
tie(A, B) = T;
ss.upd(A, -B);
}
act.clear();
ms.upd(s[b[i]], i);
}
}
