// Starcraft 2 enjoyer //
#include <bits/stdc++.h>
using namespace std;
#define LSOne(X) ((X) & -(X))
const int N = 1e5 + 5;
const int M = 3e6 + 5;
const int LG = 20;
const int C = 26;
const long long INF = 1e18 + 5;
const int P = 31;
const int MOD = 998244353;
struct Fenwick
{
vector<int> ft;
int n;
Fenwick(int len)
{
n = len;
ft.assign(n + 1, 0);
}
void update(int pos, int val)
{
while (pos <= n)
{
ft[pos] += val;
pos += LSOne(pos);
}
}
int get(int pos)
{
int sum = 0;
while (pos > 0)
{
sum += ft[pos];
pos -= LSOne(pos);
}
return sum;
}
int get(int l, int r)
{
if (l > r)
return 0;
return get(r) - get(l - 1);
}
};
int n, a[N], d[N], par[N], id[N], cid, top[N], bigchild[N], depth[N];
pair<int, int> edges[N];
vector<int> adj[N];
vector<pair<int, int>> val[N], cur, temp;
int dfs1(int c, int p)
{
par[c] = p;
int sz = 1, x = -1;
for (int i : adj[c])
{
if (i == p)
continue;
depth[i] = depth[c] + 1;
int j = dfs1(i, c);
sz += j;
if (j > x)
{
bigchild[c] = i;
x = j;
}
}
return sz;
}
void dfs2(int c, int p)
{
id[c] = cid++;
top[c] = p;
val[p].push_back({a[c], depth[c]});
if (bigchild[c] == -1)
{
reverse(val[p].begin(), val[p].end());
return;
}
dfs2(bigchild[c], p);
for (int i : adj[c])
{
if (i == bigchild[c] || i == par[c])
continue;
dfs2(i, i);
}
}
void lift(int c, int v)
{
for (; c != 0; c = par[top[c]])
{
// for(auto &[a, b] : val[top[c]])
// {
// cout << a << " " << b << "\n";
// }
// cout << "v\n";
while (!val[top[c]].empty() && val[top[c]].back().second <= depth[c])
{
temp.push_back(val[top[c]].back());
val[top[c]].pop_back();
}
if (!val[top[c]].empty())
{
temp.push_back({val[top[c]].back().first, depth[c]});
}
val[top[c]].push_back({v, depth[c]});
while (!temp.empty())
{
cur.push_back(temp.back());
temp.pop_back();
}
}
}
int get()
{
int m = 0, ans = 0;
vector<int> v;
for(auto &[i, j] : cur)
{
v.push_back(i);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
Fenwick ft(v.size());
for(int x = 0; x < cur.size(); x++)
{
// cout << cur[x].first << " " << cur[x].second << "\n";
int len = x == cur.size() -1 ? cur[x].second : cur[x].second - cur[x + 1].second;
cur[x].first = lower_bound(v.begin(), v.end(), cur[x].first) - v.begin() + 1;
ans += len * ft.get(cur[x].first - 1);
ft.update(cur[x].first, len);
}
return ans;
}
void solve()
{
cin >> n;
for (int x = 1; x <= n; x++)
{
cin >> a[x];
d[x] = a[x];
bigchild[x] = -1;
}
for (int x = 0; x < n - 1; x++)
{
int a, b;
cin >> a >> b;
adj[a].push_back(b);
edges[x] = {a, b};
}
depth[1] = 1;
dfs1(1, 0);
dfs2(1, 1);
for (int x = 0; x < n - 1; x++)
{
cur.clear();
lift(edges[x].first, a[edges[x].second]);
cout << get() << "\n";
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
for (int x = 1; x <= t; x++)
{
solve();
}
return 0;
}
