#include <bits/stdc++.h>
using namespace std;
void setup()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
struct FENWICK_TREE
{
int tree[100001], tree_size;
inline void Init(int new_size)
{
tree_size = new_size;
fill_n(tree, tree_size + 1, 0);
}
inline void Add(int x, int v)
{
while (x <= tree_size)
{
tree[x] += v;
x += (x & (~(x - 1)));
}
}
inline int Get(int x)
{
int res = 0;
while (0 < x)
{
res += tree[x];
x -= (x & (~(x - 1)));
}
return res;
}
} ft;
int n;
int a[100000], b[100000], c[100000], d[100000];
int depth[100000], sz[100000], head[100000], par[100000];
vector<int> g[100000];
vector<pair<int, int>> v[100000], cur, temp;
inline bool Comp(const int &ina, const int &inb)
{
return sz[ina] > sz[inb];
}
inline void DFS(int node)
{
sz[node] = 1;
for (auto &i : g[node])
{
depth[i] = depth[node] + 1;
par[i] = node;
DFS(i);
sz[node] += sz[i];
}
sort(g[node].begin(), g[node].end(), Comp);
}
inline void HLD(int node, int chain)
{
head[node] = (chain == -1 ? node : chain);
for (int i = 0; i < g[node].size(); ++i)
{
HLD(g[node][i], (i == 0 ? head[node] : -1));
}
}
inline void GoUp(int node, int new_val)
{
temp.clear();
while (!v[head[node]].empty() && v[head[node]].back().second <= depth[node])
{
temp.push_back(v[head[node]].back());
v[head[node]].pop_back();
}
if (!v[head[node]].empty())
{
temp.push_back({v[head[node]].back().first, depth[node]});
}
v[head[node]].push_back({new_val, depth[node]});
while (!temp.empty())
{
cur.push_back(temp.back());
temp.pop_back();
}
if (par[head[node]] != -1)
{
GoUp(par[head[node]], new_val);
}
}
inline long long Val(vector<pair<int, int>> &inp)
{
int m;
long long res = 0, h;
for (int i = 0; i < inp.size(); ++i)
{
d[i] = inp[i].first;
}
sort(d, d + inp.size());
m = unique(d, d + inp.size()) - d;
ft.Init(m);
for (int i = 0; i < inp.size(); ++i)
{
inp[i].first = lower_bound(d, d + m, inp[i].first) - d + 1;
h = (i == inp.size() - 1 ? inp[i].second : inp[i].second - inp[i + 1].second);
res += h * (ft.Get(inp[i].first - 1));
ft.Add(inp[i].first, h);
}
return res;
}
int main()
{
setup();
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> c[i];
d[i] = c[i];
}
for (int i = 0; i < n - 1; ++i)
{
cin >> a[i] >> b[i];
a[i]--;
b[i]--;
g[a[i]].push_back(b[i]);
}
depth[0] = 1;
par[0] = -1;
v[0].push_back({c[0], 1});
DFS(0);
HLD(0, -1);
sort(d, d + n);
for (int i = 0; i < n - 1; ++i)
{
cur.clear();
GoUp(b[i], c[b[i]]);
cout << Val(cur) << "\n";
}
return 0;
}
