#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;
const int maxN = 100'000;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using vvi = vector<vi>;
using pii = pair<int, int>; //liveliness, count
using vpii = vector<pii>;
int N;
vi C(1+maxN);
vi A(maxN), B(maxN);
vi parent(1+maxN, 0);
vi childlist[1+maxN];
vi subtree(1+maxN, 1);
vi chain(1+maxN, 0);
int chain_ct = 0;
vi chain_head(1+maxN, 0);
deque<pii> chain_list[1+maxN];
vi depth(1+maxN, 0);
void dfs(int u)
{
int main_child = -1;
for(int v: childlist[u])
{
depth[v] = 1 + depth[u];
dfs(v);
subtree[u] += subtree[v];
if(main_child == -1 || subtree[v] > subtree[main_child])
main_child = v;
}
if(main_child == -1)
{
chain_ct++;
chain[u] = chain_ct;
}
else
chain[u] = chain[main_child];
chain_head[ chain[u] ] = u;
}
deque<pii> lst;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N;
for(int i = 1; i <= N; i++) cin >> C[i];
for(int j = 1; j <= N-1; j++)
{
cin >> A[j] >> B[j];
parent[B[j]] = A[j];
childlist[A[j]].push_back(B[j]);
}
dfs(1);
// for(int i = 1; i <= N; i++) cerr << chain[i] << ' ';
// cerr << '\n';
chain_list[ chain[1] ].push_back(make_pair(C[1], 1));
for(int j = 1; j <= N-1; j++)
{
// cerr << "\n\n\n";
// cerr << "j = " << j << ": \n";
lst.clear();
// cerr << A[j] << " -> " << B[j] << '\n';
vpii query_markers;
for(int c = A[j]; c != 0; c = parent[ chain_head[ chain[ c ] ] ])
{
// cerr << "querying vertex: " << c << ", " << depth[c] - depth[ chain_head[ chain[c] ] ] + 1 << "\n";
query_markers.push_back(make_pair(chain[c], depth[c] - depth[ chain_head[ chain[c] ] ] + 1));
}
// reverse(query_markers.begin(), query_markers.end());
// for(int c = chain_head[ chain[A[j]] ]; c != 0; c = chain_head[ chain[ parent[c] ] ])
// {
// query_list.push_back(chain[c]);
// // cerr << "getting from node " << c << "\n";
// // for(pii l: chain_list[chain[c]])
// // lst.push_front(l);
// }
reverse(query_markers.begin(), query_markers.end());
for(auto q: query_markers)
{
int f = q.second;
int cf = 0;
for(pii l: chain_list[q.first])
{
int r_cf = min(f-cf, l.second);
cf += r_cf;
// lst.push_back(l);
lst.push_back(make_pair(l.first, r_cf));
if(cf == f) break;
}
}
// reverse(lst.begin(), lst.end());
int ls = int(lst.size());
// for(pii q: lst) cerr << q.first << ' ' << q.second << " | ";
// cerr << '\n';
vi I(ls);
for(int i = 0; i < ls; i++)
{
I[i] = i;
}
sort(I.begin(), I.end(), [] (int u, int v)
{
if(lst[u].first != lst[v].first) return lst[u].first > lst[v].first;
else return u > v;
});
ll ans = 0;
vll BIT(1 + ls, 0);
for(int i:I)
{
for(int q = i+1; q >= 1; q -= q&-q)
ans += BIT[q] * lst[i].second;
for(int q = i+1; q <= ls; q += q&-q)
BIT[q] += lst[i].second;
}
cout << ans << '\n';
chain_list[chain[B[j]]].push_back(make_pair(C[B[j]], 1));
deque<pii> update_chains;
for(int c = B[j]; c != 0; c = parent[ chain_head[ chain[c] ] ])
{
// cerr << "updating vertex " << c << '\n';
update_chains.push_front(make_pair(chain[c], depth[c] - depth[ chain_head[ chain[c] ] ] + 1));
}
for(pii u: update_chains)
{
// cerr << "u = " << u.first << ' ' << u.second << '\n';
int origin_remain = u.second;
int remain = u.second;
int c = u.first;
while(remain > 0)
{
int rx = chain_list[c][0].second;
int r = min(remain, rx);
chain_list[c][0].second -= r;
remain -= r;
if(chain_list[c][0].second == 0)
chain_list[c].pop_front();
}
chain_list[c].push_front(make_pair(C[B[j]], origin_remain));
// cerr << "pushing " << origin_remain << " of " << C[B[j]] << " at the head of chain " << c << '\n';
}
// for(int c = B[j]; c != 0; c = parent[ chain_head[ chain[c] ] ])
// {
// cerr << "updating " << chain[c] << " = " << C[B[j]] << ", " << depth[c] - depth[ chain_head[ chain[c] ] ] + 1 << '\n';
// chain_list[chain[c]].clear();
// chain_list[chain[c]].push_back(make_pair(C[B[j]], depth[c] - depth[ chain_head[ chain[c] ] ] + 1));
// }
}
}
