#include<bits/stdc++.h>
#define newl '\n'
const int N = 1e5 + 10;
const int V = 1e7 + 10;
const long long INF = 1e18;
const long long M = 1e9 + 7;
struct FenwickTree{
std::vector<int> bit;
FenwickTree(int n) : bit(n + 1,0){
}
void update(int idx,int v){
for(int i = idx;i < (int)bit.size();i += (i & (-i))){
bit[i] += v;
}
}
int sum(int idx){
int ans = 0;
for(int i = idx;i > 0;i -= (i & (-i))){
ans += bit[i];
}
return ans;
}
};
struct Node{
int min_val,max_val,lazy;
Node() : min_val(0),max_val(0),lazy(-1){
}
Node operator + (const Node &other) const {
Node res;
res.min_val = std::min(min_val,other.min_val);
res.max_val = std::max(max_val,other.max_val);
res.lazy = -1;
return res;
}
};
struct SegmentTree{
int n;
std::vector<Node> st;
SegmentTree(int n) : n(n),st(n * 4 + 10,Node()){
}
private:
void down(int id){
if(st[id].lazy != -1){
st[id << 1].min_val = st[id << 1].max_val = st[id << 1].lazy = st[id].lazy;
st[id << 1 | 1].min_val = st[id << 1 | 1].max_val = st[id << 1 | 1].lazy = st[id].lazy;
st[id].lazy = -1;
}
}
void update(int l,int r,int u,int v,long long val,int id = 1){
if(u <= l && r <= v){
st[id].min_val = st[id].max_val = st[id].lazy = val;
return;
}
down(id);
int mid = (l + r) / 2;
if(v <= mid){
update(l,mid,u,v,val,id << 1);
}else if(u > mid){
update(mid + 1,r,u,v,val,id << 1 | 1);
}else{
update(l,mid,u,v,val,id << 1);
update(mid + 1,r,u,v,val,id << 1 | 1);
}
st[id] = st[id << 1] + st[id << 1 | 1];
}
Node query(int l,int r,int u,int v,int id = 1){
if(u <= l && r <= v){
// assert(st[id].max_val != -1);
return st[id];
}
down(id);
int mid = (l + r) / 2;
if(v <= mid){
return query(l,mid,u,v,id << 1);
}
if(u > mid){
return query(mid + 1,r,u,v,id << 1 | 1);
}
return query(l,mid,u,v,id << 1) + query(mid + 1,r,u,v,id << 1 | 1);
}
int walk(int l,int r,int pos,int v,int id = 1){
if((st[id].min_val == v && st[id].max_val == v) || l > pos){
return -1;
}
if(l == r){
// std::cout << "IMP " << st[id].min_val << " " << st[id].max_val << newl;
// exit(0);
return l;
}
down(id);
int mid = (l + r) / 2;
int ans = walk(mid + 1,r,pos,v,id << 1 | 1);
if(ans != -1){
return ans;
}
return walk(l,mid,pos,v,id << 1);
}
public:
void update(int l,int r,long long w){
update(1,n,l,r,w);
}
Node query(int l,int r){
if(l > r){
return Node();
}
return query(1,n,l,r);
}
int walk(int pos,int v){
return walk(1,n,pos,v);
}
};
struct Solver{
int n,timer;
std::vector<std::vector<int>> adj;
std::vector<int> c,order,f,par,tp,in,ver;
Solver() : timer(0){
}
void readData(){
std::cin >> n;
adj.resize(n + 1);
c.assign(n + 1,0);
order.assign(n + 1,0);
f.assign(n + 1,0);
par.assign(n + 1,0);
tp.assign(n + 1,0);
in.assign(n + 1,0);
ver.assign(n + 1,0);
for(int i = 1;i <= n;++i){
std::cin >> c[i];
}
for(int i = 2;i <= n;++i){
int u,v;
std::cin >> u >> v;
adj[u].emplace_back(v);
order[i] = v;
}
}
void prepare(){
std::set<int> s(c.begin() + 1,c.end());
std::vector<int> v(s.begin(),s.end());
for(int i = 1;i <= n;++i){
c[i] = std::upper_bound(v.begin(),v.end(),c[i]) - v.begin();
}
}
void get_size(int u = 1){
f[u] = 1;
for(int &v : adj[u]){
par[v] = u;
get_size(v);
f[u] += f[v];
if(f[v] > f[adj[u][0]]){
std::swap(v,adj[u][0]);
}
}
}
void dfs(int u = 1){
in[u] = ++timer;
ver[timer] = u;
for(int v : adj[u]){
tp[v] = (v == adj[u][0] ? tp[u] : v);
dfs(v);
}
}
void solve(){
SegmentTree T(n);
FenwickTree bit(n);
T.update(1,1,c[1]);
std::vector<std::pair<int,int>> v;
auto prepare = [&](int u){
u = par[u];
while(u != 0){
// std::cerr << u << newl;
int cur = T.query(in[u],in[u]).max_val;
int it = T.walk(in[u],cur);
if(it < in[tp[u]]){
v.emplace_back(cur,in[u] - in[tp[u]] + 1);
u = par[tp[u]];
}else{
v.emplace_back(cur,in[u] - it);
u = ver[it];
}
}
};
auto cnt_contribute = [&](int u) -> long long{
prepare(u);
long long ans = 0;
// std::reverse(v.begin(),v.end());
for(std::pair<int,int> cur : v){
// if(u == 5){
// std::cout << cur.first << " " << cur.second << newl;
// }
ans += bit.sum(cur.first - 1) * (long long)cur.second;
bit.update(cur.first,cur.second);
}
for(std::pair<int,int> cur : v){
bit.update(cur.first,-cur.second);
}
v.clear();
return ans;
};
auto update = [&](int u){
int v = c[u];
while(u != 0){
T.update(in[tp[u]],in[u],v);
u = par[tp[u]];
}
};
for(int i = 2;i <= n;++i){
std::cout << cnt_contribute(order[i]) << newl;
update(order[i]);
}
}
void main(){
readData();
prepare();
get_size();
tp[1] = 1;
dfs();
solve();
}
};
int main(){
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);std::cout.tie(nullptr);
Solver().main();
return 0;
}
/*
5
12923 10000 230 9012 100000
1 2
2 3
2 4
3 5
*/
