// ~Be name khoda~ //
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define cl clear
#define endll '\n'
const int maxn = 1e6 + 10;
const int maxn5 = 1e5 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 2e18;
int ind = 1;
set <pair<int, int>> av[maxn5];
vector <int> have, liv, req, adj[maxn5];
ll fen[maxn5];
int sz[maxn5], big[maxn5], h[maxn5];
int par[maxn5], f[maxn5], fid[maxn5];
int fir[maxn5], a[maxn5];
inline void add(int id, ll val){
for(; id < maxn5; id += id & -id){
fen[id] += val;
have.pb(id);
}
return;
}
inline ll get(int id){
ll ret = 0;
for(; id; id -= id & -id)
ret += fen[id];
return ret;
}
inline void dfs_det(int v){
sz[v] = 1;
big[v] = -1;
for(auto u : adj[v]){
h[u] = h[v] + 1;
dfs_det(u);
sz[v] += sz[u];
par[u] = v;
if(big[v] == -1 || sz[big[v]] <= sz[u])
big[v] = u;
}
return;
}
inline void dfs_hld(int v, int last, int id){
f[v] = last;
fid[v] = id;
//cout << v << ' ' << f[v] << ' ' << fid[v] << endl;
if(last == v)
fir[id] = -h[v] + 1;
av[id].insert({-h[v], maxn5 - 5});
//cout << "then why ? " << v << ' ' << av[id].size() << endl;
if(big[v] != -1){
dfs_hld(big[v], last, id);
}
for(auto u : adj[v]) if(u != big[v]){
dfs_hld(u, u, ind++);
}
return;
}
inline ll solve(int v, int val){
if(v == -1) return 0;
//cout << "aha " << v << ' ' << val << endl;
int id = fid[v];
auto it = av[id].lower_bound(mp(-h[v], -1));
auto itt = it;
itt--;
ll ret = 0;
if(h[v] > (it->fi) * -1){
int len = (it == av[id].end() ? fir[id] : (it->fi)) + h[v];
if((itt->se) > 1)
ret += get((itt->se) - 1) * len;
add(itt->se, len);
//cout << "begor " << ' ' << (itt->fi) << ' ' << (itt->se) << ' ' << len << ' ' << ret << endl;
}
for(; it != av[id].end();){
itt = it;
int len = 0;
itt++;
if(itt != av[id].end())
len = (itt->fi) - (it->fi);
else
len = fir[id] - (it->fi);
itt--;
if((it -> se) > 1)
ret += get((it->se) - 1) * len;
add(it->se, len);
//cout << "Look " << (it->fi) << ' ' << (it->se) << ' ' << len << ' ' << ret << ' ' << fir[id] << endl;
it++;
av[id].erase(itt);
}
av[id].insert({-h[v], val});
ret += solve(par[f[v]], val);
return ret;
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n; cin >> n;
for(int i = 0; i < n; i++){
cin >> a[i];
liv.pb(a[i]);
}
sort(all(liv));
liv.resize(unique(all(liv)) - liv.begin());
for(int i = 0; i < n; i++)
a[i] = (lower_bound(all(liv), a[i]) - liv.begin()) + 1;
for(int i = 0; i < n - 1; i++){
int a, b; cin >> a >> b;
a--; b--;
adj[a].pb(b);
req.pb(b);
}
par[0] = -1;
dfs_det(0);
dfs_hld(0, 0, 0);
for(auto u : req){
have.clear();
ll ans = solve(u, a[u]);
cout << ans << '\n';
for(auto v : have)
fen[v] = 0;
}
}
