#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=1e5+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,a[maxn]; vector<int>E[maxn]; int siz[maxn],mxs[maxn],vis[maxn]; vector<int>nd; void dfs(int u,int fa){ siz[u]=1,mxs[u]=0;nd.p_b(u); for(int x:E[u])if(x!=fa&&(!vis[x]))dfs(x,u),siz[u]+=siz[x],mxs[u]=max(mxs[u],siz[x]); } struct Trie { struct nd { int ls,rs,siz; ll sum,tot;int lz; void add(int x){ lz+=x,sum+=siz*x; } }d[maxn*8]; int cnt; #define ls(p) d[p].ls #define rs(p) d[p].rs int nnd(){ int p=++cnt; ls(p)=rs(p)=0; d[p].siz=d[p].sum=d[p].tot=d[p].lz=0; return p; } void clear(){ up(i,0,cnt)ls(i)=rs(i)=d[i].siz=d[i].sum=d[i].tot=d[i].lz=0; cnt=0; } void pu(int p){ d[p].siz=d[p].sum=d[p].tot=0; if(ls(p))d[p].siz+=d[ls(p)].siz,d[p].sum+=d[ls(p)].sum,d[p].tot+=d[ls(p)].tot; if(rs(p))d[p].siz+=d[rs(p)].siz,d[p].sum+=d[rs(p)].sum; } void pd(int p){ if(ls(p))d[ls(p)].add(d[p].lz); if(rs(p))d[rs(p)].add(d[p].lz); d[p].lz=0; } void ins(int x){ int p=0; vector<int>v={0}; up(i,0,19){ if((x>>i)&1){ if(!rs(p))rs(p)=nnd(); p=rs(p); }else { if(!ls(p))ls(p)=nnd(); p=ls(p); } v.p_b(p); } d[p].sum+=x,d[p].siz++,d[p].tot++; v.pop_back(),reverse(v.begin(),v.end()); for(int x:v)pu(x); } void add(int u){ if(!u)return;pd(u); swap(ls(u),rs(u)); add(ls(u));//d[rs(u)].add(1); pu(u); } void upd(){ d[0].add(1);pd(0);swap(ls(0),rs(0));add(ls(0));pu(0); } ll query(int p,int dep,int fl){ if(!p)return 0; ll res=0;pd(p); if(rs(p)){ ll sum=d[rs(p)].sum-d[rs(p)].tot*1ll*(1<<dep+1); if(fl)sum-=d[rs(p)].siz; res=sum>>dep; } res+=query(ls(p),dep+1,fl); return res; } ll qry(){ ll res=0;pd(0); if(ls(0))res+=query(ls(0),0,0); if(rs(0))res+=query(rs(0),0,1); return res; } }T; int dep[maxn]; void dfs2(int u,int fa){ nd.p_b(u);dep[u]=dep[fa]+1; for(int x:E[u])if((!vis[x])&&x!=fa)dfs2(x,u); } vector<int>Q[maxn]; vector<int>G[maxn]; vector<int>qry[maxn]; ll res[maxn]; void solve(int u){ vector<int>son; for(int x:E[u])if(!vis[x])son.p_b(x);dep[u]=0; for(int x:son)nd.clear(),dfs2(x,u),Q[x]=nd; int mxd=0; for(int x:son)for(int p:Q[x])T.ins(a[p]+dep[p]-1),mxd=max(mxd,dep[p]); T.ins(a[u]-1); qry[0]={u}; for(int x:son)for(int p:Q[x])qry[dep[p]].p_b(p); up(i,0,mxd){ ll ans=T.qry(); for(int p:qry[i])res[p]+=ans; T.upd(); }T.clear(); up(i,0,mxd)qry[i].clear(); for(int x:son){ int mxd=0; for(int p:Q[x])mxd=max(mxd,dep[p]),T.ins(a[p]+dep[p]-1); for(int p:Q[x])qry[dep[p]].p_b(p); up(i,0,mxd){ ll ans=T.qry(); for(int p:qry[i])res[p]-=ans; T.upd(); } T.clear(); up(i,0,mxd)qry[i].clear(); } for(int x:son)Q[x].clear(),Q[x].shrink_to_fit(); } void dfs3(int u){ vis[u]=1;solve(u); for(int x:E[u])if(!vis[x]){ nd.clear();dfs(x,u); for(int p:nd)mxs[p]=max(mxs[p],(int)nd.size()-siz[p]); int rt=nd[0];for(int p:nd)if(mxs[p]<mxs[rt])rt=p; dfs3(rt); } } void slv(){ n=read(); up(i,1,n)a[i]=read(); up(i,1,n-1){ int x=read(),y=read(); E[x].p_b(y),E[y].p_b(x); } dfs3(1); up(i,1,n)printf("%lld ",res[i]); } int main(){ //freopen("team.in","r",stdin),freopen("team.out","w",stdout); slv(); return 0; }