#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 5, maxN = 4e5 + 5, lg = 18;
int n;
bool vis[maxn];
int a[maxn];
vector<int> adj[maxn];
int newid[maxn], out[maxn], cnt = 0;
int binlift[maxn][lg];
void dfs(int u) {
cnt++;
newid[u] = cnt;
for (int i=1;i<lg;i++) {
if (!binlift[u][i-1]) break;
binlift[u][i] = binlift[binlift[u][i-1]][i-1];
}
for (int v:adj[u]) {
adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
binlift[v][0] = u;
dfs(v);
}
out[u] = cnt;
}
int seg[maxN];
void update(int id, int l, int r, int target, int val) {
if (r < target || target < l) return;
if (l == r) {
seg[id] = val;
return;
}
int mid = (l+r)/2;
update(id*2, l, mid, target, val); update(id*2+1, mid+1, r, target, val);
seg[id] = max(seg[id*2], seg[id*2+1]);
}
int mx(int id, int l, int r, int findl, int findr) {
if (r < findl || findr < l) return 0;
if (findl <= l && r <= findr) return seg[id];
int mid = (l+r)/2;
return max(mx(id*2, l, mid, findl, findr), mx(id*2+1, mid+1, r, findl, findr));
}
struct thing {
int val, freq, id;
bool operator < (const thing &b) const {
return val > b.val;
}
};
int fen[maxn];
void fenupdate(int id, int val) {
while (id <= n) {
fen[id] += val;
id += (id & -id);
}
}
int sum(int id) {
int val = 0;
while (id >= 1) {
val += fen[id];
id -= (id & -id);
}
return val;
}
int solve(vector<pair<int,int>> VEC) {
// for (auto [x, y]:VEC) cout << x << " " << y << endl;
int sz = VEC.size();
vector<thing> vec;
for (int i=0;i<sz;i++) vec.push_back({VEC[i].first, VEC[i].second, i});
sort(vec.begin(), vec.end());
vector<pair<int,int>> temp;
int ans = 0, last = -1;
for (int i=0;i<=sz;i++) fen[i] = 0;
for (auto [val, freq, id]:vec) {
if (val != last) {
for (auto [x, j]:temp) fenupdate(j+1, x);
temp.clear();
}
ans += sum(id+1);
temp.push_back({freq, id+1});
}
return ans;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i=1;i<=n;i++) cin >> a[i];
pair<int,int> qry[n+1];
vis[1] = true;
qry[1] = {0, 1};
for (int i=2;i<=n;i++) {
int u, v;
cin >> u >> v;
if (vis[u]) qry[i] = {u, v}, vis[v] = true;
else qry[i] = {v, u}, vis[u] = true;
adj[u].push_back(v); adj[v].push_back(u);
}
dfs(1);
update(1, 1, n, 1, 1);
for (int i=2;i<=n;i++) {
auto [u, v] = qry[i];
vector<pair<int,int>> vec = {{a[v], 0}};
while (true) {
int cmp = mx(1, 1, n, newid[v], out[v]);
for (int i=lg-1;i>=0;i--) {
int cur = binlift[v][i];
if (cur && mx(1, 1, n, newid[cur], out[cur]) == cmp) v = cur, vec.back().second += (1<<i);
}
v = binlift[v][0];
if (v == 0) break;
// cout << newid[u] << " " << out[u] << endl;
// cout << v << " " << mx(1, 1, n, newid[v], out[v]) << endl;
vec.push_back({a[qry[mx(1, 1, n, newid[v], out[v])].second], 1});
}
reverse(vec.begin(), vec.end());
vec.pop_back();
cout << solve(vec) << endl;
update(1, 1, n, newid[qry[i].second], i);
// if (i==1) cout << v << " " << newid[v] << endl;
}
}
