//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 1e5;
vector<int> adj[N + 1];
int nchain, chain[N + 1], head[N + 1], pos[N + 1], timer, sz[N + 1];
int n, par[N + 1], b[N + 1], c[N + 1];
vector<pair<int, int> > dp[N + 1];
struct FenwickTree
{
int Tree[N + 1];
void add(int pos, int val)
{
for (; pos <= n; pos |= pos + 1)
{
Tree[pos] += val;
}
}
int sum(int pos)
{
int ret = 0;
for (; pos >= 0; pos = (pos & (pos + 1)) - 1)
{
ret += Tree[pos];
}
return ret;
}
int sum(int l, int r)
{
return sum(r) - sum(l - 1);
}
} tree;
void read()
{
vector<int> id;
cin >> n;
for (int i = 1; i <= n; ++ i)
{
cin >> c[i];
id.push_back(i);
}
sort(id.begin(), id.end(), [&](const int &x, const int &y)
{
return c[x] < c[y];
});
int pre = -1, t = 0;
for (int i : id)
{
if (c[i] != pre)
{
++ t;
pre = c[i];
}
c[i] = t;
//cerr << c[i] << ' ';
}
//cerr << '\n';
for (int i = 1; i < n; ++ i)
{
int u, v;
cin >> u >> v;
adj[u].push_back(v);
par[v] = u;
b[i] = v;
}
}
void preDFS(int u)
{
sz[u] = 1;
for (int v : adj[u])
{
preDFS(v);
sz[u] += sz[v];
}
}
void HLD(int u)
{
if (head[nchain] == 0)
{
head[nchain] = u;
}
chain[u] = nchain;
pos[u] = ++timer;
int bigchild = -1;
for (int v : adj[u])
{
if (bigchild == -1 || sz[v] > sz[bigchild])
{
bigchild = v;
}
}
if (bigchild != -1)
{
HLD(bigchild);
}
for (int v : adj[u])
{
if (v == bigchild)
{
continue;
}
++nchain;
HLD(v);
}
}
void solve()
{
preDFS(1);
HLD(1);
dp[0] = {{1, c[1]}};
for (int i = 1; i < n; ++ i)
{
long long res = 0;
int u = par[b[i]];
vector<pair<int, int> > total;
int color = c[b[i]];
while(u > 0)
{
vector<pair<int, int> > f;
int v = head[chain[u]];
int pre = pos[head[chain[u]]] - 1;
//cerr << u << ' ' << pre << ' ' << pos[u] - pos[pre] << '\n';
while(!dp[chain[u]].empty() && pos[dp[chain[u]].back().first] <= pos[u])
{
f.emplace_back(pos[dp[chain[u]].back().first] - pre, dp[chain[u]].back().second);
pre = pos[dp[chain[u]].back().first];
dp[chain[u]].pop_back();
}
if (!dp[chain[u]].empty())
{
f.emplace_back(pos[u] - pre, dp[chain[u]].back().second);
}
dp[chain[u]].emplace_back(u, color);
u = par[v];
move(f.begin(), f.end(), back_inserter(total));
while(!f.empty())
{
res += 1LL * f.back().first * tree.sum(f.back().second - 1);
tree.add(f.back().second, f.back().first);
//cerr << f.back().first << ' ' << f.back().second << '\n';
f.pop_back();
}
}
dp[chain[b[i]]] = {{b[i], c[b[i]]}};
for (auto &p : total)
{
tree.add(p.second, -p.first);
}
cout << res ;
cout << '\n';
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
//freopen(TASK".OUT", "w", stdout);
}
int t = 1;
bool typetest = false;
if (typetest)
{
cin >> t;
}
for (int __ = 1; __ <= t; ++ __)
{
//cout << "Case " << __ << ": ";
read();
solve();
}
}
