#include<bits/stdc++.h> #include<bits/extc++.h> using namespace std; #define int long long #define lson t[pos][0] #define rson t[pos][1] #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define pb push_back #define inx(u) int I=h[(u)],v=edge[I].v;I;I=edge[I].nx,v=edge[I].v int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;} const int MAXN=100010,N=22,inf=1e18,Mod=1e9+7; struct Edge{int v,nx;}edge[MAXN<<1];int h[MAXN],CNT;void add_side(int u,int v){edge[++CNT]={v,h[u]};h[u]=CNT;edge[++CNT]={u,h[v]};h[v]=CNT;} int n,m,q,a[MAXN],f[MAXN],d[MAXN],as[MAXN]; struct Trie{ int t[MAXN<<3][2],lz[MAXN<<3],siz[MAXN<<3],sum[MAXN<<3],sht[MAXN<<3],cnt,id; void cln(){cnt=1,sht[cnt]=sum[cnt]=siz[cnt]=t[cnt][0]=t[cnt][1]=lz[cnt]=0;} int p[N]; void insert(int x){ int pos=1; for(int i=0;i<N;i++){ p[i]=pos; int op=x>>i&1; if(!t[pos][op])t[pos][op]=++cnt,sht[cnt]=sum[cnt]=siz[cnt]=t[cnt][0]=t[cnt][1]=lz[cnt]=0; pos=t[pos][op]; } sum[pos]+=x,siz[pos]++,sht[pos]++; for(int i=N-1;~i;i--)pushup(p[i]); } void upd(int pos,int x){ sum[pos]+=x*siz[pos]; lz[pos]+=x; } void pushdown(int pos){ if(lz[pos]){ upd(lson,lz[pos]),upd(rson,lz[pos]); lz[pos]=0; } } void pushup(int pos){ if(!lson&&!rson)return; siz[pos]=siz[lson]+siz[rson]; sum[pos]=sum[lson]+sum[rson]; sht[pos]=sht[lson]; } void add(int pos){ pushdown(pos); if(rson)add(rson); upd(lson,1); swap(lson,rson); pushup(pos); } int qry(int pos,int tmp){ pushdown(pos); int res=sum[rson]-sht[rson]*tmp; if(lson)res+=qry(lson,tmp<<1)>>1; return res; } }T[2]; bool OP; void cln(){T[0].cln(),T[1].cln(),OP=0;} bool vis[MAXN]; int siz[MAXN]; void ins(int u,int lst,int dep){ siz[u]=1; T[(dep+a[u])&1].insert((dep+a[u])>>1); for(inx(u))if(!vis[v]&&v!=lst)ins(v,u,dep+1),siz[u]+=siz[v]; } struct node{ int u,lst,dep; }; queue<node>Q; int bfs(int s,int lst,int sz,int op){ int mn=inf,id=0,lsd=0; Q.push({s,lst,op==0}); while(!Q.empty()){ int u=Q.front().u,dep=Q.front().dep,lst=Q.front().lst;Q.pop(); if(lsd!=dep)T[OP^1].add(1),OP^=1,lsd++; int mx=sz-siz[u]; int tmp=T[0].qry(1,1)+T[1].qry(1,1); as[u]+=op?tmp:-tmp; for(inx(u))if(v!=lst&&!vis[v]){ Q.push({v,u,dep+1}); mx=max(mx,siz[v]); } if(mx<mn)mn=mx,id=u; } return id; } void dfs(int u){ vector<int>G; ins(u,u,0); bfs(u,u,0,1); cln(); for(inx(u))if(!vis[v]){ ins(v,u,1); int tmp=bfs(v,u,siz[v],0); G.pb(tmp); cln(); } vis[u]=1; for(auto o:G)dfs(o); } void slv(){T[0].id=0,T[1].id=1; n=read(); for(int i=1;i<=n;i++)a[i]=read()-1; for(int i=1;i<n;i++){ int u=read(),v=read(); add_side(u,v); } cln(); dfs(1); for(int i=1;i<=n;i++)printf("%lld ",as[i]<<1); } signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); slv(); // cerr<<(clock()*1.0)/CLOCKS_PER_SEC<<"s"<<endl; return 0; }