#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<long long, long long> ii;
int n;
int cnt = 0;
int arr[100005];
int low[100005];
int high[100005];
int p[100005][20];
vector<int> adj[100005];
vector<ii> edges;
///segment tree
ii tree[200005];
int timer = 1;
void update(int i, int v){
for(i += n;i > 0;i >>= 1) tree[i] = ii(timer, v);
timer++;
}
ii query(int u){
int l = low[u], r = high[u];
ii res = ii(0,0);
for(l += n, r += n+1;l < r;l >>= 1, r >>= 1){
if(l&1) res = max(res, tree[l++]);
if(r&1) res = max(res, tree[--r]);
}
return res;
}
///segment tree
///segment tree 2
int tree2[100005];
void update2(int i, int v){
for(i += n;i > 0;i >>= 1) tree2[i] += v;
}
long long query2(int l, int r){
long long res = 0;
for(l += n, r += n;l < r;l >>= 1, r >>= 1){
if(l&1) res += tree2[l++];
if(r&1) res += tree2[--r];
}
return res;
}
///segment tree 2
void dfs(int u, int P){
low[u] = cnt; cnt++;
high[u] = low[u];
for(int v : adj[u]){
if(v == P) continue;
dfs(v, u);
p[v][0] = u;
high[u] = max(high[u], high[v]);
}
update(low[u], arr[u]);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
vector<int> discrodile;
for(int i = 1;i <= n;i++){
cin >> arr[i];
discrodile.push_back(arr[i]);
}
sort(discrodile.begin(), discrodile.end());
discrodile.erase(unique(all(discrodile)), discrodile.end());
for(int i = 1;i <= n;i++){
arr[i] = lower_bound(all(discrodile), arr[i]) - discrodile.begin();
}
for(int i = 1;i < n;i++){
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
edges.push_back(ii(u,v));
}
dfs(1,0);
for(int d = 1;d <= 19;d++){
for(int i = 1;i <= n;i++){
p[i][d] = p[p[i][d-1]][d-1];
//cout << p[i][d] << " ";
}
//cout << "\n";
}
for(ii e : edges){
int u = e.first, v = e.second; ///extend tree from u to v;
//cout << "\n" << u << " " << v << ":\n";
vector<ii> parts;
while(true){
ii root = query(u);
int sz = 1;
for(int d = 19;d >= 0;d--){
int nu = p[u][d];
if(nu == 0) continue;
if(query(nu) != root) continue;
u = nu;
sz += (1 << d);
}
//cout << root.first << " " << root.second << " " << sz << "\n";
parts.push_back(ii(root.second, sz));
if(u == 1) break;
u = p[u][0];
}
long long ans = 0;
for(ii x : parts){
ans += x.second * query2(0, x.first);
update2(x.first, x.second);
}
for(ii x : parts) update2(x.first, -x.second); ///undo
cout << ans << "\n";
update(low[v], arr[v]);
}
}
