#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ld = long double;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
#define int ll
const int MOD = 998244353;
int N, timer, C[100005], X[100005], Y[100005];
int tin[100005], dep[100005], S[100005], T[100005];
vector<int> adj[100005]; deque<pair<int, int>> sub[100005];
int P[400005], ST[400005];
int dfs_size(int v, int p) {
P[v] = p; dep[v] = dep[p] + 1; S[v] = 1;
for(auto u : adj[v]) {
if(u == p) continue;
S[v] += dfs_size(u, v);
}
return S[v];
}
void getHeavy(int v, int p, int top) {
tin[v] = timer++; T[v] = top;
int heavy = -1, cur = 0;
for(auto u : adj[v]) {
if(u == p) continue;
if(S[u] > cur)
cur = S[u], heavy = u;
}
if(heavy == -1) return;
getHeavy(heavy, v, top);
for(auto u : adj[v]) {
if(u == p || u == heavy) continue;
getHeavy(u, v, u);
}
}
int _N;
void init(int n) {
_N = n;
for(int l = 0; l <= _N; l++) ST[l] = 0;
}
void update(int p, int v) {
for(; p <= _N; p += (p & (-p)))
ST[p] += v;
}
int query(int p) {
int res = 0;
for(; p; p -= (p & (-p)))
res += ST[p];
return res;
}
int solve(int v) {
vector<pair<int, int>> E; vector<int> comp;
while(v != -1) {
int top = T[v];
int d = dep[v] - dep[top] + 1;
vector<pair<int, int>> A;
for(int i = 0; i < sub[top].size(); i++) {
int k = sub[top][i].first; int cur = sub[top][i].second;
if(k <= d) {
A.push_back({k, cur});
d -= k; continue;
}
A.push_back({d, cur});
break;
}
for(int l = A.size() - 1; ~l; l--) {
E.push_back(A[l]); comp.push_back(A[l].second);
}
v = P[top];
}
reverse(E.begin(), E.end());
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
int ans = 0, tot = 0; init(comp.size());
for(auto u : E) {
u.second = lower_bound(comp.begin(), comp.end(), u.second) - comp.begin();
ans += u.first * (tot - query(++u.second ));
tot += u.first;
update(u.second, u.first);
}
return ans;
}
void add(int v, int cur) {
while(v != -1) {
int top = T[v], d = dep[v] - dep[top] + 1;
while(!sub[top].empty()) {
int k = sub[top][0].first;
if(k <= d) {
sub[top].pop_front();
d -= k; continue;
}
sub[top].front().first -= d;
break;
}
sub[top].push_front({dep[v] - dep[top] + 1, cur});
v = P[top];
}
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N;
for(int l = 1; l <= N; l++)
cin >> C[l];
for(int l = 0; l < N - 1; l++) {
cin >> X[l] >> Y[l];
adj[X[l]].push_back(Y[l]);
adj[Y[l]].push_back(X[l]);
}
dep[1] = -1; dfs_size(1, 1); getHeavy(1, 1, 1);
P[1] = -1; add(1, C[1]);
for(int l = 0; l < N - 1; l++) {
int U = X[l], V = Y[l];
cout << solve(U) << "\n";
add(V, C[V]);
}
return 0;
}
