#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 1e5 + 5;
const int maxv = 1e5;
const int inf = 1e9;
struct node {
int l,r,val;
node(int _l = 0, int _r = 0, int _val = 0) {
l = _l; r = _r; val = _val;
}
bool operator < (node a) const {
if(a.l!=l) return l<a.l;
if(a.r!=r) return r<a.r;
return val<a.val;
}
};
int n;
int a[maxn];
vector<int> way[maxn];
pii e[maxn];
map<int,int> mp;
int par[maxn];
int sz[maxn], bigc[maxn];
int m, cid[maxn], cpos[maxn];
int csz[maxn], chead[maxn];
set<node> itv[maxn];
int tree[maxv+5];
ll res;
vector<pii> all;
vector<node> sad;
void dfs(int u, int last) {
sz[u] = 1;
for(auto v : way[u]) {
if(v==last) continue;
par[v] = u;
dfs(v, u);
sz[u] += sz[v];
if(sz[v] > sz[bigc[u]]) bigc[u] = v;
}
}
void init(int u, int last) {
cid[u] = m; cpos[u] = ++csz[m];
if(cpos[u]==1) chead[m] = u;
if(bigc[u]) init(bigc[u],u);
for(auto v : way[u]) {
if(v==last || v==bigc[u]) continue;
m++; init(v, u);
}
}
void update(int x, int val) {
if(val>0) all.push_back({x,val});
while(x<=maxv) {
tree[x] += val;
x += x&-x;
}
}
int query(int x) {
int res = 0;
while(x) {
res += tree[x];
x -= x&-x;
}
return res;
}
void calc(int x, int val) {
if(val==-1) return ;
res += (ll)query(x-1)*val;
update(x,val);
}
ll solve(int u) {
// printf("solving\n");
// printf("---- solve %d\n",u);
int x = cid[u];
// for(auto t : itv[x]) printf("\t\t(%d, %d, %d)\n",t.l,t.r,t.val);
auto it = (--itv[x].upper_bound(node(cpos[u],inf,inf)));
while(it!=itv[x].end()) {
// printf("\t\tcalc %d : [%d, %d]\n",it->val,it->l,min(cpos[u],it->r));
calc(it->val,min(cpos[u],it->r)-it->l+1);
if(it==itv[x].begin()) break;
it--;
}
if(chead[x]!=1) solve(par[chead[x]]);
}
void go(int u, int val) {
// printf("---- go %d : %d\n",u,val);
int x = cid[u];
// for(auto t : itv[x]) printf("\t\t(%d, %d, %d)\n",t.l,t.r,t.val);
node tmp;
for(auto it : itv[x]) {
if(it.l>cpos[u]) break;
tmp = it;
sad.push_back(tmp);
}
for(auto t : sad) itv[x].erase(t);
sad.clear();
itv[x].insert(node(1,cpos[u],val));
if(tmp.l!=0 && cpos[u]<tmp.r) itv[x].insert(node(cpos[u]+1,tmp.r,tmp.val));
if(chead[x]!=1) go(par[chead[x]],val);
}
void cpidx() {
int cur = 0;
for(int i=1;i<=n;i++) mp[a[i]];
for(auto &t : mp) t.second = ++cur;
for(int i=1;i<=n;i++) a[i] = mp[a[i]];
}
int main() {
// freopen("03-09.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
cpidx();
for(int i=1;i<=n-1;i++) {
int u,v; scanf("%d%d",&u,&v);
way[u].push_back(v); way[v].push_back(u);
e[i] = {u,v};
}
dfs(1,0);
m = 1; init(1,0);
for(int i=1;i<=m;i++) itv[i].insert(node(1,csz[i],-1));
// for(int i=1;i<=n;i++) printf("%d : id = %d pos = %d (%d)\n",i,cid[i],cpos[i],chead[cid[i]]);
go(1,a[1]);
for(int i=1;i<=n-1;i++) {
res = 0;
solve(e[i].X);
go(e[i].Y, a[e[i].Y]);
for(auto t : all) update(t.X,-t.Y);
all.clear();
printf("%lld\n",res);
}
}
