#include <bits/stdc++.h>
#ifdef LOCAL
#include <bits/debug.hpp>
#endif // LOCAL
#define ll long long
#define all(x) x.begin(), x.end()
#define Neco "Construction of Highway"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 1e5 + 7
using namespace std;
const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;
int n;
int a[maxn], h[maxn], par[maxn];
int nex[maxn], In[maxn], siz[maxn];
vector<int> edges[maxn];
vector<pair<int, int>> P[maxn];
pair<int, int> E[maxn];
/// DATA STRUCTURE
struct BIT {
int bit[maxn];
void update(int x, int val) {
for(; x < maxn; x += (x & -x)) bit[x] += val;
}
int get(int x, int ans = 0) {
for(; x > 0; x -= (x & -x)) ans += bit[x];
return ans;
}
} Bit;
/// PRE DFS
int dfs_siz(int u) {
siz[u] = 1;
for(int &v : edges[u]) {
edges[v].erase(find(all(edges[v]), u));
h[v] = h[u] + 1, par[v] = u;
siz[u] += dfs_siz(v);
if(siz[v] > siz[edges[u][0]]) swap(v, edges[u][0]);
}
return siz[u];
}
void dfs_hld(int u) {
static int Time = 0;
In[u] = ++Time;
for(int v : edges[u]) {
if(v == edges[u][0]) nex[v] = nex[u];
else nex[v] = v;
dfs_hld(v);
}
}
/// HLD DECOMP <3
ll get(int u, int val) {
ll ans = 0;
vector<pair<int, int>> S, tmp;
auto prog = [&](int u, int p) {
int prv = h[p] - 1;
tmp.clear();
while(!P[p].empty() && h[P[p].back().first] < h[u]) {
tmp.push_back({P[p].back().second, h[P[p].back().first] - prv});
prv = h[P[p].back().first];
P[p].pop_back();
}
if(!P[p].empty()) tmp.push_back({P[p].back().second, h[u] - prv});
P[p].push_back({u, val});
reverse(all(tmp));
for(auto x : tmp) S.push_back(x);
};
for(; u != 0; u = par[nex[u]]) {
prog(u, nex[u]);
}
for(auto [cl, w] : S) ans += 1ll * w * Bit.get(cl - 1), Bit.update(cl, w);
for(auto [cl, w] : S) Bit.update(cl, -w);
return ans;
}
void solve()
{
vector<int> Comp;
cin >> n;
fi(i, 1, n) cin >> a[i], Comp.push_back(a[i]);
fi(i, 1, n - 1) {
int x, y; cin >> x >> y;
E[i] = {x, y};
edges[x].push_back(y), edges[y].push_back(x);
}
resp(Comp);
fi(i, 1, n) a[i] = upper_bound(all(Comp), a[i]) - Comp.begin();
nex[1] = h[1] = 1;
dfs_siz(1), dfs_hld(1);
get(1, a[1]);
fi(i, 1, n - 1) {
int x, y; tie(x, y) = E[i];
cout << get(y, a[y]) << '\n';
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen(Neco".inp", "r")) {
freopen(Neco".inp", "r", stdin);
freopen(Neco".out", "w", stdout);
}
int nTest = 1;
// cin >> nTest;
while(nTest--)
{
solve();
}
return 0;
}
