# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair <int, int >
using namespace std;
const int N = 1e5 + 5;
int lv[N],sz[N],par[N],tree[N],in[N],out[N],tin,sizeofchain[N];
map <int, int> shes;
vector <int> v[N],tocomp;
vector < pii > vec[N];
int bigchild[N],chain[N],n,a[N],b[N],c[N];
void update(int idx, int val) {
for (int i = idx; i < N; i += i&(-i)) {
tree[i] += val;
}
}
int getans(int idx) {
int pas = 0;
for (int i = idx; i > 0; i-=i&(-i)) {
pas += tree[i];
}
return pas;
}
void dfs(int a, int p) {
sz[a] = 1;
lv[a] = lv[p] + 1;
par[a] = p;
for (int i = 0; i < v[a].size(); i++) {
int to = v[a][i];
if (to == p) continue;
dfs(to,a);
sz[a] += sz[to];
if (!bigchild[a] || sz[bigchild[a]] < sz[to]) {
bigchild[a] = to;
}
}
}
void dfs1(int a, int p) {
tin++;
in[a] = tin;
if (bigchild[a]) dfs1(bigchild[a],a);
for (int i = 0; i < v[a].size(); i++) {
int to = v[a][i];
if (to == p || to == bigchild[a]) continue;
dfs1(to,a);
}
out[a] = tin;
}
void dfs_chain(int a,int p) {
if (bigchild[a]) {
chain[bigchild[a]] = chain[a];
}
sizeofchain[a]++;
if (!vec[chain[a]].size()) {
vec[chain[a]].pb({c[a],1});
} else {
if (vec[chain[a]].back().f == c[a]) {
vec[chain[a]].back().s++;
} else vec[chain[a]].pb({c[a],1});
}
for (int i = 0; i < v[a].size(); i++) {
int to = v[a][i];
if (to == p) continue;
dfs_chain(to,a);
}
}
int getans(int a, int b) {
int ans = 0;
int lst = chain[a];
int cur = a;
vector <pii> pas;
//if (a == 2 && b == 3) cout<<lst<<"\n",prnt(vec[lst]);
while (true) {
lst = chain[cur];
int x = lv[cur] - lv[lst] + 1;
//if (a == 5 && b == 9) cout<<lst<<" "<<cur<<endl;
vector <pii> vv;
int sum = 0;
for (int i = 0; i < vec[lst].size(); i++) {
if(vec[lst][i].s + sum > x) {
// if (a == 5 && b == 9 && lst == 1) cout<<x<<" "<<sum<<" "<< (x - sum)<<endl;
vv.pb({vec[lst][i].f, (x - sum)});
break;
}
sum += vec[lst][i].s;
vv.pb({vec[lst][i].f,vec[lst][i].s});
if (sum == x) break;
}
reverse(vv.begin(),vv.end());
for (int i = 0; i < vv.size(); i++) {
pas.pb({vv[i].f,vv[i].s});
}
cur = par[lst];
if (cur == 0) break;
}
//if (a == 2 && b == 3)cout<<endl<<endl,
//prnt(pas);
// cout<<a<<" "<<b<<endl;
// prnt(pas);
for (int i = 0; i < pas.size(); i++) {
ans += getans(pas[i].f - 1)*pas[i].s;
update(pas[i].f, pas[i].s);
}
for (int i = 0; i < pas.size(); i++) update(pas[i].f, -pas[i].s);
return ans;
}
void toadd(int a, int b) {
int lst = chain[a];
int cur = a;
while (true) {
lst = chain[cur];
int x = lv[cur] - lv[lst] + 1;
int sum = 0; int idx = 0;
vector <pii> vv;
vv.pb({c[b],x});
for (int i = 0; i < vec[lst].size(); i++) {
if (vec[lst][i].s + sum > x) {
vv.pb({vec[lst][i].f,vec[lst][i].s - (x - sum)});
idx = i + 1;
break;
}
sum += vec[lst][i].s;
idx = i + 1;
if (sum == x) break;
}
for (int i = idx; i < vec[lst].size(); i++) {
vv.pb({vec[lst][i].f,vec[lst][i].s});
}
vec[lst].clear();
for (int i = 0; i < vv.size(); i++) {
if (!vec[lst].size()) vec[lst].pb(vv[i]);
else {
if (vec[lst].back().f == vv[i].f) vec[lst].back().s += vv[i].s;
else vec[lst].pb({vv[i].f,vv[i].s});
}
}
cur = par[lst];
if (cur == 0) break;
}
}
main() {
std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
cin>>n;
for (int i = 1; i <= n; i++) {
cin>>c[i];
tocomp.pb(c[i]);
}
sort(tocomp.begin(),tocomp.end());
int cnt = 1;
shes[tocomp[0]] = 1;
for (int i = 1; i < tocomp.size(); i++) {
if (tocomp[i] != tocomp[i - 1]) cnt++;
shes[tocomp[i]] = cnt;
}
for (int i = 1; i <= n; i++) c[i] = shes[c[i]];
for (int i = 1; i <= n - 1; i++) {
cin>>a[i]>>b[i];
v[a[i]].pb(b[i]);
v[b[i]].pb(a[i]);
}
for (int i = 1; i <= n; i++) {
chain[i] = i;
}
dfs(1,0);
dfs1(1,0);
dfs_chain(1,0);
for (int i = 1; i <= n - 1; i++) {
int ss = getans(a[i],b[i]);
toadd(a[i],b[i]);
cout<<ss<<endl;
}
}
