#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define szz(r) (ll)r.size()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
const int mxn=1e5+5;
ll fw[mxn]{0};
vector<int>tmp;
void add(int i,int amt){
i=upper_bound(all(tmp),i)-tmp.begin();
for(;i<mxn;i+=i&-i)fw[i]+=amt;
}
ll qr(int i,ll rs=0){
i=upper_bound(all(tmp),i)-tmp.begin();
for(;i;i-=i&-i)rs+=fw[i];
return rs;
}
vector<int>g[mxn];
int s[mxn]{0};
int a[mxn],b[mxn],sz[mxn],pr[mxn]{0},head[mxn]{0},id[mxn]{0},cur=0;
void dfs(int u,int p){
sz[u]=1;pr[u]=p;
for(auto v:g[u]){
if(v==p)continue;
dfs(v,u);sz[u]+=sz[v];
}
}
void hld(int u,int p,int tp){
head[u]=tp;id[u]=++cur;
int hv=-1;
for(auto v:g[u]){
if(v==p)continue;
if(hv==-1||sz[hv]<sz[v])hv=v;
}if(hv==-1)return;
hld(hv,u,tp);
for(auto v:g[u]){
if(v==p||v==hv)continue;
hld(v,u,v);
}
}
deque<pair<pii,int>>dq[mxn];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>s[i],tmp.pb(s[i]);
sort(all(tmp));tmp.erase(unique(all(tmp)),tmp.end());
for(int i=1;i<=n-1;i++){
cin>>a[i]>>b[i];g[a[i]].pb(b[i]);g[b[i]].pb(a[i]);
}dfs(1,-1);hld(1,1,1);dq[1].push_front({{1,1},s[1]});
for(int i=1;i<=n-1;i++){
int x=a[i],y=b[i];
vector<pair<pii,int>>rs;
stack<pair<pii,int>>st;
while(x!=-1){
while(!dq[head[x]].empty()){
auto it = dq[head[x]].front();
if(it.f.s<=id[x])st.push(it),dq[head[x]].pop_front();
else if(it.f.f<=id[x]){
dq[head[x]].pop_front();
dq[head[x]].push_front({{id[x]+1,it.f.s},it.s});
st.push({{it.f.f,id[x]},it.s});
break;
}else break;
}while(!st.empty())rs.pb(st.top()),st.pop();
dq[head[x]].push_front({{id[head[x]],id[x]},s[y]});
x=pr[head[x]];
}if(dq[head[y]].empty())dq[head[y]].pb({{id[y],id[y]},s[y]});
else dq[head[y]].back().f.s=id[y],dq[head[y]].back().s=s[y];
ll ans=0;
for(auto it : rs)ans+=qr(it.s-1)*(it.f.s-it.f.f+1),add(it.s,it.f.s-it.f.f+1);
cout<<ans<<'\n';
for(auto it : rs)add(it.s,-it.f.s+it.f.f-1);
}
}
