#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a); i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"debug"<<endl
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
const int NINF = 0x3f3f3f40;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0x3f3f3f3f3f3f3f40;
const int mxN = 100001;
int n;
int cnt = 0;
ttgl inout[mxN];
ttgl edges[mxN];
set<int> stt;
map<int, int> mp;
int arr[mxN];
int seg[4*mxN];
int par[mxN][18];
vector<int> adj[mxN];
void upd(int p, int val) {
for(seg[p+=2*n] = val; p>1; p>>=1) seg[p>>1] = max(seg[p], seg[p^1]);
}
int qmax(int l, int r) {
int res = 0;
r++;
for(l+=2*n, r+=2*n; l<r; l>>=1, r>>=1) {
if(l&1) res= max(res, seg[l++]);
if(r&1) res = max(res, seg[--r]);
}
return res;
}
int BIT[mxN];
void add(int i, int val) {
while(i<=n) {
BIT[i]+= val;
i +=i&-i;
}
}
void del(int i) {
while(i<=n) {
BIT[i] = 0;
i +=i&-i;
}
}
int sum (int i) {
int res = 0;
while(i>0) {
res+=BIT[i];
i-=i&-i;
}
return res;
}
void dfs(int u, int p) {
par[u][0] = p;
inout[u].first = cnt++;
for(int v: adj[u]) {
if(v==p)continue;
dfs(v, u);
}
inout[u].second = cnt++;
}
int query(int k) {
//cout<<"\n";
//cout<<k<<" "<<inout[k].first<<" "<<inout[k].second<<" "<<qmax(inout[k].first, inout[k].second)<<" hi\n";
return qmax(inout[k].first, inout[k].second);
}
int main()
{
//freopen("filename.in", "r", stdin);
//freopen("filename.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
cin>>n;
owo(i, 0, n) {
cin>>arr[i];
stt.insert(arr[i]);
}
int idx = 0;
auto it = stt.begin();
while(it!=stt.end()) {
mp[*it] = idx++;
it++;
}
owo(i, 0, n) {
arr[i] = mp[arr[i]];
}
owo(i, 0, n-1) {
cin>>edges[i].first>>edges[i].second;
edges[i].first--;
edges[i].second--;
adj[edges[i].first].senpai(edges[i].second);
adj[edges[i].second].senpai(edges[i].first);
}
dfs(0, -1);
owo(lg, 1, 18) {
owo(i, 0, n) {
if(par[i][lg-1]==-1) {
par[i][lg] = -1;
}else {
par[i][lg] = par[par[i][lg-1]][lg-1];
}
}
}
owo(i, 0, 2*mxN) {
seg[i] = -1;
}
upd(inout[0].first, 0);
owo(i, 1, n) {
int a = edges[i-1].first;
int b = edges[i-1].second;
int ans = 0;
vector<int> path;
//cout<<i<<"\n";
int val = query(a)==0 ? arr[a] : arr[edges[query(a)-1].second];
while(a!=-1) {
int num= 1;
//cout<<a<<" ";
uwu(i, 18, 0) {
if(par[a][i]!=-1&&query(par[a][i])==query(a)) {
a = par[a][i];
num+=(1<<i);
}
}
//cout<<a<<" "<<num<<" "<<val<<" "<<sum(val+1)<<"\n";
ans+=num*sum(val);
add(val+1, num);
path.senpai(val+1);
a = par[a][0];
val = arr[edges[query(a)-1].second];
//cout<<query(a)<<"\n";
}
memset(BIT, 0, sizeof(BIT));
cout<<ans<<"\n";
upd(inout[b].first, i);
//cout<<inout[b].first<<" "<<i<<" cool\n";
}
return 0;
}
