#include <bits/stdc++.h>
using namespace std;
const int Nmax = 1e5 + 5;
typedef long long ll;
struct Val
{
int val, cnt;
};
vector<int> v[Nmax];
vector<Val> A;
int n, x[Nmax], y[Nmax], val[Nmax], t[Nmax];
struct AIB
{
int a[Nmax], n;
int ub(int x) { return (x&(-x)); }
void update(int pos, int val)
{
for(; pos; pos-=ub(pos)) a[pos] += val;
}
int query(int pos)
{
int ans = 0;
for(; pos<=n; pos+=ub(pos)) ans += a[pos];
return ans;
}
void shrink(int n)
{
this->n = n;
int i;
for(i=0; i<=n; ++i) a[i] = 0;
}
} aib;
namespace hld
{
static int where[Nmax], pos[Nmax], w[Nmax];
static vector<int> p[Nmax];
static deque<Val> z[Nmax];
void dfs(int node)
{
w[node] = 1;
for(auto son : v[node])
{
dfs(son);
w[node] += w[son];
}
}
void prepare_chains(int node)
{
static int chains = 1;
where[node] = chains;
p[where[node]].push_back(node);
pos[node] = p[where[node]].size();
if(v[node].empty()) return;
int xson = v[node][0];
for(auto son : v[node])
if(w[son] > w[xson]) xson = son;
prepare_chains(xson);
for(auto son : v[node])
if(son != xson)
{
++chains;
prepare_chains(son);
}
}
void path(int node, vector<Val> &A)
{
int s = 0, i, id = where[node], len = pos[node];
vector<Val> curr;
for(i=0; i<z[id].size() && s + z[id][i].cnt <= len; ++i)
{
curr.push_back(z[id][i]);
s += z[id][i].cnt;
}
if(i < z[id].size())
curr.push_back({ z[id][i].val, len - s });
reverse(curr.begin(), curr.end());
for(auto it : curr) A.push_back(it);
if(id == 1) return;
path(t[p[id][0]], A);
}
void update(int node, int val)
{
int id = where[node], len = pos[node];
while(z[id].size() && len >= z[id][0].cnt) len -= z[id][0].cnt, z[id].pop_front();
if(z[id].empty() && len == 1) /// this is the chain that includes the new node
{
z[id].push_back({val, pos[node]});
if(id == 1) return;
update(t[p[id][0]], val);
return;
}
/// otherwise the current chain is a "normal" one
if(z[id].size())
z[id][0].cnt -= len;
else assert(len == 0);
z[id].push_front({val, pos[node]});
if(id == 1) return;
update(t[p[id][0]], val);
}
};
ll solve(vector<Val> &A) /// count the number of inversions
{
reverse(A.begin(), A.end());
map<int,int> mp;
for(auto it : A) mp[it.val] = 1;
int cnt = 1;
for(auto &it : mp) it.second = ++cnt;
for(auto &it : A) it.val = mp[it.val];
aib.shrink(cnt);
ll ans = 0;
for(auto &it : A)
{
ans += (ll) aib.query(it.val + 1) * it.cnt;
aib.update(it.val, it.cnt);
}
return ans;
}
int main()
{
// freopen("input", "r", stdin);
cin.sync_with_stdio(false);
int i;
cin >> n;
for(i=1; i<=n; ++i) cin >> val[i];
for(i=1; i<n; ++i)
{
cin >> x[i] >> y[i];
v[x[i]].push_back(y[i]);
t[y[i]] = x[i];
}
hld :: dfs(1);
hld :: prepare_chains(1);
hld :: z[1].push_back({val[1], 1});
for(i=1; i<n; ++i)
{
A.clear();
hld :: path(x[i], A);
cout << solve(A) << '\n';
hld :: update(y[i], val[y[i]]);
}
return 0;
}
