#include <cstdio>
#include <vector>
#include <algorithm>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef long long ll;
typedef pair < int, int > pii;
const int N = 1e5 + 500;
const int LOG = 17;
const int OFF = (1 << LOG);
ll inv, ans[N];
vector < int > saz, v[N];
int loga[N], siz = 0, koga[N], C[N], n, cur;
int A[N], B[N], L[N], R[N];
int vrh[N], dep[N], dno[N], par[N][LOG], lan[N];
void add(int x, int y){
siz += y;
for(; x < N ; x += x & -x)
loga[x] += y;
}
int query(int x){
int ret = 0;
for(; x ; x -= x & -x)
ret += loga[x];
return ret;
}
void dfs(int x,int lst){
par[x][0] = lst; dep[x] = dep[lst] + 1;
L[x] = cur++;
for(int y : v[x])
dfs(y, x);
R[x] = cur - 1;
}
void precompute(){
for(int j = 1;j < LOG;j++)
for(int i = 1;i <= n;i++)
par[i][j] = par[par[i][j - 1]][j - 1];
}
int digni(int x,int k){
for(int i = LOG - 1;i >= 0;i--)
if(k & (1 << i)) x = par[x][i];
return x;
}
int tour[2 * OFF];
void update(int i,int x){
tour[i + OFF] = x;
for(i = (i + OFF) / 2; i ; i /= 2)
tour[i] = max(tour[2 * i], tour[2 * i + 1]);
}
int query(int i,int a,int b,int lo,int hi){
if(lo <= a && b <= hi) return tour[i];
if(a > hi || b < lo) return 0;
return max(query(2 * i, a, (a + b) / 2, lo, hi), query(2 * i + 1, (a + b) / 2 + 1, b, lo, hi));
}
int gdje(int i){
return query(1, 0, OFF - 1, L[i], R[i]);
}
ll odradi(int st){
int x = gdje(st);
ll inv = 0;
vector < pii > brisi;
for(;;){
inv += (ll)query(C[dno[x]] - 1) * (dep[st] - dep[vrh[x]] + 1);
add(C[dno[x]], dep[st] - dep[vrh[x]] + 1);
brisi.PB({C[dno[x]], dep[st] - dep[vrh[x]] + 1});
int ol_vrh = vrh[x];
if(st != dno[x]){
vrh[x] = digni(dno[x], dep[dno[x]] - dep[st] - 1);
}
if(!(ol_vrh - 1)) break;
st = par[ol_vrh][0];
x = gdje(st);
}
for(pii tmp : brisi)
add(tmp.X, -tmp.Y);
return inv;
}
int main(){
scanf("%d", &n);
for(int i = 1;i <= n;i++){
scanf("%d", C + i), saz.PB(C[i]);
}
sort(saz.begin(), saz.end());
for(int i = 1;i <= n;i++)
C[i] = lower_bound(saz.begin(), saz.end(), C[i]) - saz.begin() + 1;
for(int i = 1;i < n;i++){
scanf("%d%d", A + i, B + i);
v[A[i]].PB(B[i]);
}
dfs(1, 1); precompute();
vrh[0] = 1, dno[0] = 1;
for(int i = 1;i < n;i++){
printf("%lld\n", odradi(A[i]));
dno[i] = B[i], vrh[i] = 1;
update(L[B[i]], i);
}
}
