#include <bits/stdc++.h>
using namespace std;
#define int long long
//#define pb push_back
int inf = 1e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
struct bitt {
vector<int> t;
int n;
bitt (int N) : n(N+1) {
t.resize(n+2);
};
void upd(int i, int va) { i ++ ;
for(; i < n; i += (i & -i)) t[i] += va;
};
int get(int i) { i ++ ;
int res = 0;
for(; i > 0; i -= (i & -i)) res += t[i];
return res;
};
int get(int l, int r) { r--;
return get(r ) - get( -- l );
};
}bt(N);
vector<vector<int>> g(N);
vector<vector<array<int,2>>> lst(N);
int sz[N], pr[N], head[N], heavy[N], dep[N], id[N];
int tim = 1;
void dfs(int ps, int par) {
sz[ps] = 1;
pr[ps] = par;
heavy[ps] = 0;
for(int to : g[ps]) {
if(to == par)continue;
dep[to] = dep[ps] + 1;
dfs(to, ps);
sz[ps] += sz[to];
if(sz[heavy[ps]] < sz[to]) heavy[ps] = to;
}
}
void hld(int ps, int hd) {
head[ps] = hd;
id[ps] = tim ++ ;
if(heavy[ps])
hld(heavy[ps], hd);
for(int to : g[ps]){
if(to == pr[ps] || to == heavy[ps])continue;
hld(to, to);
}
};
int query(int ps) {
vector<array<int,2>> ord;
while(1) {
int to = head[ps];
int ds = dep[ps] - dep[to] + 1;
vector<array<int,2>> res;
int la = 0;
for(int i = lst[to].size()-1; i >= 0; i -- ) {
auto [x, y] = lst[to][i];
res.push_back({x, min(ds,y)-la});
la = y;
if(y >= ds) break;
}
reverse(res.begin(), res.end());
for(auto i : res)ord.push_back(i);
if(to == 1) break;
ps = pr[to];
}
int ans = 0;
for(auto [x, y] : ord) {
ans += bt.get(x-1) * y;
bt.upd(x, y);
}
for(auto [x, y] : ord) bt.upd(x, -y);
return ans;
};
void upd (int ps, int va) {
while(1) {
int to = head[ps];
int ds = dep[ps] - dep[to] + 1;
while(lst[to].size() && lst[to].back()[1] <= ds)lst[to].pop_back();
lst[to].push_back({va, ds});
if(to == 1)return;
ps = pr[to];
}
};
void solve(){
int n; cin >> n;
vector<int> a(n+1);
for(int i = 1; i <= n; i++ )cin >> a[i];
vector<int> b = a;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
for(int i = 1; i <= n; i ++ )a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
vector<array<int,2>> ed(n-1);
for(auto &[a, b] : ed) {
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1, 1);
hld(1, 1);
lst[1].push_back({a[1], 1});
for(auto [u, v] : ed) {
//cout << 1 << '\n';
//for(auto [x, y] : lst[1])cout << x << ' ' << y << '\n';
//cout << 3 << '\n';
//for(auto [x, y] : lst[3])cout << x << ' ' << y << '\n';
//cout << 6 << '\n';
//for(auto [x, y] : lst[6])cout << x << ' ' << y << '\n';
//cout << 7 << '\n';
//for(auto [x, y] : lst[7])cout << x << ' ' << y << '\n';
//cout << "ans" << '\n';
cout << query(u) << '\n';
upd(v, a[v]);
};
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while(tt -- ){
solve();
};
};
