#pragma GCC optimization O2
#pragma GCC optimization "unroll-loop"
#pragma target ("avx2")
#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e5 + 9;
const ll Log2 = 20;
const ll inf = 1e9 + 7;
vector<ll> g[N];
LL edge[N];
ll n,a[N],x,y,head[N],child[N],par[N],curSZ,d[N];
deque<LL> chain[N];
void DFS_sz(ll u){
child[u] = 1;
ll mx = 0;
for (ll i = 0;i < g[u].size();i++){
ll v = g[u][i];
DFS_sz(v); child[u] += child[v];
if (child[v] > mx) mx = child[v],swap(g[u][0],g[u][i]);
}
}
void DFS_hld(ll u){
for (auto i : g[u]){
par[i] = u; d[i] = d[u] + 1;
if (i == g[u][0]) head[i] = head[u];
else head[i] = i; DFS_hld(i);
}
}
ll bit[N];
void Clear(){
for (ll i = 1;i <= curSZ;i++) bit[i] = 0;
}
void upd(ll p,ll val){
for (ll i = p;i <= curSZ;i += i & -i) bit[i] += val;
}
ll Get(ll p){
ll res = 0;
for (ll i = p;i > 0;i -= i & -i) res += bit[i];
return res;
}
void AddEdge(ll u,ll val){
while(u != -1){
ll nu = head[u],sz = d[u] - d[nu] + 1;
while(!chain[nu].empty()){
LL now = chain[nu].front();
if (sz < now.fs){
chain[nu].front().fs -= sz;
break;
}
else{
sz -= now.fs; chain[nu].pop_front();
}
}
chain[nu].push_front({d[u] - d[nu] + 1,val}); u = par[nu];
}
}
void compress(deque<LL> &v){
vector<ll> now;
for (auto i : v) now.push_back(i.sc);
sort(now.begin(),now.end()); now.resize(unique(now.begin(),now.end()) - now.begin());
for (ll i = 0;i < v.size();i++){
ll cur = lower_bound(now.begin(),now.end(),v[i].sc) - now.begin() + 1;
v[i].sc = cur;
}
}
void out(deque<LL> dq){
for (auto i : dq) cout<<i.fs<<" "<<i.sc<<"\n";
exit(0);
}
ll Query(ll u){
deque<LL> v; ll root = u;
while(u != -1){
vector<LL> tmp;
ll nu = head[u],sz = d[u] - d[nu] + 1;
for (auto i : chain[nu]){
if (!sz) break;
ll p = min(sz,i.fs);
sz -= p; tmp.push_back({p,i.sc});
}
reverse(tmp.begin(),tmp.end());
for (auto i : tmp) v.push_front(i);
u = par[nu];
}
reverse(v.begin(),v.end());
curSZ = v.size(); Clear(); compress(v);
//if (root == 3){
//cout<<head[3]; exit(0);
//out(v);
//}
ll ans = 0;
for (auto i : v){
upd(i.sc,i.fs); ans += i.fs * Get(i.sc - 1);
}
//if (root == 3) cout<<ans;
return ans;
}
int main(){
ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
#define task "tst"
if (fopen(task".INP","r")){
freopen(task".INP","r",stdin);
//freopen(task".OUT","w",stdout);
}
cin>>n;
for (ll i = 1;i <= n;i++) cin>>a[i];
for (ll i = 1;i < n;i++){
cin>>x>>y; edge[i] = {x,y};
g[x].push_back(y);
}
DFS_sz(1); head[1] = 1; DFS_hld(1); par[1] = -1; //cout<<d[4]; return 0;
chain[1].push_back({1,a[1]});
for (ll i = 1;i < n;i++){
cout<<Query(edge[i].fs)<<"\n";
//Query(edge[i].fs);
AddEdge(edge[i].sc,a[edge[i].sc]);
//if (edge[i].sc == 4) out(chain[1]);
}
}
