#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef int64_t ll;
#define int ll
#define her cout<<"here"<<endl;
const int N = 1e5 + 5;
vector<int> edges[N];
int a[N], v[N], par[N][20];
int tin[N], tout[N], t, d[N];
void dfs(int u){
tin[u] = ++t;
for(int j=1;j<20;j++){
par[u][j] = par[par[u][j-1]][j-1];
}
for(auto x : edges[u]){
if(x == par[u][0]) continue;
d[x] = d[u] + 1;
par[x][0] = u;
dfs(x);
}
tout[u] = t;
}
bool is(int a, int b){
return tin[a] <= tin[b] && tout[b] <= tout[a];
}
int lca(int a, int b){
assert(!is(a, b) && !is(b, a));
for(int j=19;~j;j--){
if(!is(par[a][j], b)) a = par[a][j];
}
return a;
}
struct BIT{
int tree[N];
void add(int i, int v){
for(;i<N;i+=(i&-i)) tree[i] += v;
}
int get(int i){
int r = 0;
for(;i>0;i-=(i&-i)) r += tree[i];
return r;
}
int get(int l, int r){
return get(r) - get(--l);
}
}tree;
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
vector<int> p(n); iota(p.begin(), p.end(), 1);
sort(p.begin(), p.end(), [&](int i, int j){
return (a[i] < a[j]);
});
for(int i=0,last=0,j=0;i<n;){
while(j<n && a[p[j]] == a[p[i]]) j++;
last++;
while(i < j) a[p[i]] = last, i++;
}
vector<ar<int, 2>> e;
for(int i=1;i<n;i++){
int a, b; cin >> a >> b;
e.push_back({a, b});
edges[a].push_back(b);
edges[b].push_back(a);
}
par[1][0] = 1;
dfs(1);
v[1] = 1;
for(auto [a, b] : e){
int c = 1;
vector<ar<int, 2>> t;
while(!is(v[c], b) && c != b){
//~ cout<<c<<" "<<v[c]<<" "<<b<<endl;
int u = lca(b, v[c]);
int x = lca(v[c], b);
v[x] = v[c];
t.push_back({d[u] - d[c], ::a[v[c]]});
c = u;
}
//~ assert(v[c] == a);
if(c != b) t.push_back({d[b] - d[c], ::a[v[c]]});
v[1] = b;
int res = 0;
//~ for(auto x : t) cout<<x[0]<<" ";
//~ cout<<"\n";
//~ for(auto x : t) cout<<x[1]<<" ";
//~ cout<<"\n";
for(auto x : t){
tree.add(x[1], x[0]);
res += tree.get(x[1] + 1, N) * x[0];
}
cout<<res<<"\n";
for(auto x : t){
tree.add(x[1], -x[0]);
}
}
}
