/* _In The Name Of God_ */
#include <bits/stdc++.h>
using namespace std;
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
#define pb push_back
#define F first
#define S second
#define lc id << 1
#define rc lc|1
#define mid ((l + r)/2)
// #define int long long
typedef pair<int, int> pii;
typedef long long ll;
const ll MOD = 1e9 + 7; // 998244353;
const ll INF = 1e9 + 1;
const int MXN = 2e5 + 5;
const int LOG = 23;
ll Pow(ll a, ll b) { return !b ? 1 : (Pow(a*a %MOD, b/2) * (b&1 ? a : 1)) %MOD; }
int n, h[MXN], hd[MXN], sz[MXN], val[MXN], par[MXN];
vector<pii> E, stk[MXN], V;
vector<int> adj[MXN];
void pre_dfs(int v, int p) {
sz[v] = 1;
int i = -1;
h[v] = h[p] + (v != p);
for (int k = 0; k < adj[v].size(); k++) {
int u = adj[v][k];
if (u != p) {
pre_dfs(u, v); sz[v] += sz[u];
if (i==-1 || sz[adj[v][i]] < sz[u]) i = k;
}
}
if (i != -1) swap(adj[v][0], adj[v][i]);
}
void hld_dfs(int v, int p) {
par[v] = p;
if (adj[v][0] != p) {
hd[adj[v][0]] = hd[v];
hld_dfs(adj[v][0], v);
}
for (int k = 1; k < adj[v].size(); k++) {
int u = adj[v][k];
if (u != p) {
hd[u] = u;
hld_dfs(u, v);
}
}
}
ll M_sort(int l, int r) {
if (r - l < 2) return 0;
ll inv = M_sort(l, mid) + M_sort(mid, r);
vector<pii> vec;
int p1 = l, p2 = mid;
ll sum = 0;
while (p1 < mid || p2 < r) {
if (p1 == mid) {
inv += sum * V[p2].S;
vec.pb(V[p2++]);
}
else if (p2 == r) {
vec.pb(V[p1++]);
}
else {
if (V[p2].F <= V[p1].F) {
inv += sum * V[p2].S;
vec.pb(V[p2++]);
}
else {
sum += V[p1].S;
vec.pb(V[p1++]);
}
}
}
for (int i = 0; i < vec.size(); i++) V[l+i] = vec[i];
vec.clear();
return inv;
}
void _solve() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> val[i];
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
E.pb({u, v});
}
pre_dfs(1, 1);
hd[1] = 1;
hld_dfs(1, 1);
stk[1].pb({h[1], val[1]});
for (int i = 0; i < n-1; i++) {
vector<pii> vec;
int v = E[i].S;
while (v != 1) {
vector<pii> cev;
v = par[v];
int R = hd[v], bf = h[R]-1;
while (stk[R].size() && stk[R].back().F <= h[v]) {
cev.pb({stk[R].back().S, stk[R].back().F-bf});
bf = stk[R].back().F;
stk[R].pop_back();
}
if (stk[R].size() && bf < h[v]) {
cev.pb({stk[R].back().S, h[v]-bf});
}
stk[R].pb({h[v], val[E[i].S]});
v = R;
for (int i = (int)cev.size()-1; i >= 0; i--) {
vec.pb(cev[i]);
}
}
stk[hd[E[i].S]] = {{h[E[i].S], val[E[i].S]}};
swap(V, vec);
cout << M_sort(0, V.size()) << '\n';
}
}
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
int _ = 1;
// cin >> _;
while (_--) _solve();
return 0.0;
}
