#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
int N;
ll C[MAXN];
vector<int> adj[MAXN];
int parent[MAXN], depth[MAXN], sz[MAXN], son[MAXN];
int top[MAXN], pos[MAXN], dfn_timer;
// 1. 樹狀數組 (BIT) 用於計算逆序對
ll bit[MAXN];
void update(int i, int delta) {
for (; i <= N; i += i & -i) bit[i] += delta;
}
ll query(int i) {
ll s = 0;
for (; i > 0; i -= i & -i) s += bit[i];
return s;
}
// 2. HLD 預處理
void dfs_sz(int u, int p, int d) {
parent[u] = p; depth[u] = d; sz[u] = 1;
for (int v : adj[u]) {
dfs_sz(v, u, d + 1);
sz[u] += sz[v];
if (sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs_hld(int u, int t) {
top[u] = t; pos[u] = ++dfn_timer;
if (son[u]) dfs_hld(son[u], t);
for (int v : adj[u]) {
if (v != son[u]) dfs_hld(v, v);
}
}
// 3. 管理顏色段的結構
struct Node {
int l, r, val;
bool operator<(const Node& other) const { return l < other.l; }
};
set<Node> segments;
// 拆分段 (珂朵莉樹技巧)
auto split(int p) {
auto it = segments.lower_bound({p, 0, 0});
if (it != segments.end() && it->l == p) return it;
--it;
int l = it->l, r = it->r, v = it->val;
segments.erase(it);
segments.insert({l, p - 1, v});
return segments.insert({p, r, v}).first;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> N;
vector<ll> vals;
for (int i = 1; i <= N; i++) {
cin >> C[i];
vals.push_back(C[i]);
}
// 離散化
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
auto get_val = [&](ll x) {
return lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;
};
vector<pair<int, int>> queries;
for (int i = 0; i < N - 1; i++) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
queries.push_back({u, v});
}
dfs_sz(1, 0, 1);
dfs_hld(1, 1);
// 初始化：每個城市一開始都是自己的初始值
for (int i = 1; i <= N; i++) {
segments.insert({pos[i], pos[i], get_val(C[i])});
}
for (auto& q : queries) {
int u = q.first, b_val = get_val(C[q.second]);
vector<pair<int, int>> path_segments; // {value, length}
int curr = u;
while (curr) {
int l = pos[top[curr]], r = pos[curr];
auto it_r = split(r + 1);
auto it_l = split(l);
vector<Node> temp;
for (auto it = it_l; it != it_r; ++it) temp.push_back(*it);
// HLD 跳轉是從下往上，所以存入時要反轉順序
reverse(temp.begin(), temp.end());
for (auto& node : temp) {
path_segments.push_back({node.val, node.r - node.l + 1});
}
segments.erase(it_l, it_r);
segments.insert({l, r, b_val});
curr = parent[top[curr]];
}
// 計算逆序對：從根節點往葉子節點看
reverse(path_segments.begin(), path_segments.end());
ll cost = 0;
ll total_count = 0;
for (auto& seg : path_segments) {
// 逆序對定義：s 在 t 前面且 val[s] > val[t]
// 我們統計 BIT 中比當前值大的個數
cost += (ll)seg.second * (total_count - query(seg.first));
update(seg.first, seg.second);
total_count += seg.second;
}
// 清理 BIT 以供下次使用
for (auto& seg : path_segments) update(seg.first, -seg.second);
cout << cost << "\n";
}
return 0;
}
