#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
vector<int> colors;
vector<int> time_g;
vector<int> depth;
map<int, int> m;
struct Node{
int t;
int last_m;
int color;
mutable vector<pii> cols;
bool operator<( const Node& b)const{
return t<b.t;
}
Node(int id){
t = time_g[id];
color = colors[id];
last_m =id;
//cols.push_back(pii(depth[id]-1, color));
}
};
vector<vector<pii>> adj;
void merge_pure(set<Node>&s, set<Node>&b, int prov){
for(auto e: b){
auto e2 = e;
e2.last_m = prov;
s.insert(e);
}
}
void compute_rel(set<Node>::iterator a, set<Node>::iterator b, int d){
//cout<<a->t<<" "<<b->t<<endl;
if(a->last_m!=b->last_m){
//cout<<m[a->t]+1<<" includes "<<m[b->t]+1<<endl;
a->cols.push_back(pii(d, b->color));
}
}
void merge(set<Node>&a, set<Node>& b, int id){
for(auto it = b.begin(); it!=b.end(); it++){
auto pre = a.lower_bound((*it));
if(pre!=a.end()){
it++;
if(it== b.end() || pre->t<it->t){
it--;
compute_rel(pre, it, depth[id]);
it++;
}
it--;
}
if(pre!=a.begin()){
pre--;
if(pre!=a.end() && ((*pre)<(*it))){
//cout<<"pre "<<pre->t<<" "<<it->t<<endl;
//cout<<((*pre)<(*it))<<endl;
compute_rel(it, pre, depth[id]);
}
}
a.insert(*it);
}
}
set<Node> dfs(int id){
set<Node> res;
set<Node> comp;
if(adj[id].size()>0){
vector<set<Node>> sub;
pii best = pii(0, 0);
for(auto ch: adj[id]){
sub.push_back(dfs(ch.first));
if(sub.back().size()>best.first){
best.first = sub.back().size();
best.second = sub.size()-1;
}
}
swap(res, sub[best.second]);
for(int i = 0; i<sub.size(); i++){
if(i != best.second){
merge_pure(comp, sub[i],adj[id][i].first);
}
}
}
comp.insert(Node(id));
merge(res, comp, id);
//cout<<id<<endl;
for(auto e: res){
//cout<<m[e.t]+1<<" | ";
}
//cout<<endl<<endl<<endl;
return res;
}
int merge(vector<pii>&v, int lt, int rt, int mid){
//cout<<"merging "<<lt<<" "<<rt<<" "<<mid<<endl;
vector<pii> res;
int c= 0;
int l = lt;
int r= mid+1;
int r_s =0;
for(int i = lt; i<=rt; i++){
if(l>mid){
res.push_back(v[r]);
r_s += v[r].first;
r++;
}
else if(r>rt){
res.push_back(v[l]);
c+=(r_s)*v[l].first;
l++;
}
else if(v[l].second<=v[r].second){
res.push_back(v[l]);
c+=(r_s)*v[l].first;
l++;
}
else{
res.push_back(v[r]);
r_s += v[r].first;
r++;
}
}
for(int i = lt; i<=rt; i++){
v[i] = res[i-lt];
}
return c;
}
int dpr(vector<pii>&v, int lt, int rt){
if(lt==rt){
return 0;
}
else{
//cout<<lt<<" "<<rt<<endl;
int mid = (lt+rt)/2;
int r =0;
r+=dpr(v, lt, mid);
r+=dpr(v, mid+1, rt);
r+= merge(v, lt, rt, mid);
//cout<<r<<endl;
return r;
}
}
signed main(){
int n;
cin>>n;
colors.resize(n);
adj.resize(n);
time_g.resize(n, -1);
depth.resize(n, 1);
for(int i = 0; i<n; i++){
int c;
cin>>c;
colors[i] = c;
}
m.insert(pii(-1, 0));
for(int i = 0; i<n-1; i++){
int a, b;
cin>>a>>b;
a--;b--;
time_g[b] = i;
adj[a].push_back(pii(b, i));
depth[b] = depth[a]+1;
m.insert(pii(i, b));
}
set<Node> res = dfs(0);
//cout<<res.size()<<endl;
for(auto e: res){
//cout<<"t: "<<m[e.t]+1<<" , ";
for(auto c: e.cols){
//cout<<m[c.first]+1<<" "<<c.second<<" | ";
}
//cout<<endl;
}
vector<int> ans(n-1);
for(auto e: res){
int cur= e.t;
if(cur!=-1){
int r= 0;
sort(e.cols.begin(), e.cols.end());
for(int i = e.cols.size()-1; i>0; i--){
e.cols[i].first -=e.cols[i-1].first;
}
for(auto ee:e.cols){
//cout<<ee.first<<" "<<ee.second<<" | ";
}
//cout<<endl;
r += dpr(e.cols, 0, e.cols.size()-1);
ans[cur]= r;
}
}
//cout<<"_"<<endl;
for(int i= 0; i<n-1; i++){
cout<<ans[i]<<endl;
}
}
