#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
const int INF = 1e9;
const int MAXN = 1e5 + 7;
const int BASE = (1 << 18);
int A[MAXN];
vi g[MAXN];
int parent[MAXN];
int sz[MAXN];
vector<pii> edges;
int rep[MAXN];
set<pii> segments[MAXN];
int dep[MAXN];
ll tree[2 * BASE + 7];
int n;
void dfsInit(int v, int d){
sz[v] = 1;
dep[v] = d;
for(auto ele : g[v]){
dfsInit(ele,d + 1);
sz[v] += sz[ele];
}
for(int i = 1; i < sz(g[v]); i++){
if(sz[g[v][i]] > sz[g[v][0]]){
swap(g[v][i], g[v][0]);
}
}
}
void dfsHld(int v, int r){
rep[v] = r;
if(sz(g[v]) == 0){
return;
}
dfsHld(g[v][0], r);
for(int i = 1; i < sz(g[v]); i++){
dfsHld(g[v][i], g[v][i]);
}
}
void upd(int ind, ll ch){
ind += BASE;
while(ind > 0){
tree[ind] += ch;
ind /= 2;
}
}
ll query(int v, int l, int p, int a, int b){
if(p < a || b < l || b < a){
return 0LL;
}
if(a <= l && p <= b){
return tree[v];
}
int mid = (l + p) / 2;
return (ll)query(2 * v, l, mid, a, b) + query(2 * v + 1, mid + 1, p, a, b);
}
ll countInv(vector<pii>& vec){
ll res = 0LL;
for(auto ele : vec){
res = (ll)res + (ll)ele.fi * query(1, 0, BASE - 1, ele.se + 1, BASE - 1);
upd(ele.se, ele.fi);
}
for(auto ele : vec){
upd(ele.se, -ele.fi);
}
return res;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
map<int, int> xd;
for(int i = 1; i <= n; i++){
cin >> A[i];
xd[A[i]] = 1;
}
int lol = 0;
for(auto& ele : xd){
ele.se = lol++;
}
for(int i = 1; i <= n; i++){
A[i] = xd[A[i]];
}
parent[1] = 0;
for(int i = 1; i < n; i++){
int x, y;
cin >> x >> y;
parent[y] = x;
g[x].pb(y);
edges.pb(mp(x, y));
}
segments[1].insert(mp(0, A[1]));
dfsInit(1, 0);
dfsHld(1, 1);
// for(int i = 1; i <= n; i++){
// cerr << dep[i] << ' ' << rep[i] << '\n';
// }
// cerr << "========\n";
// for(int i = 1; i <= n; i++){
// cerr << "=== " << i << '\n';
// for(auto ele : segments[i]){
// cerr << ele << '\n';
// }
// }
for(auto [a, b] : edges){
//policz wynik
vector<pii> vec = {};
while(a != 0){
vector<pii> nvec = {};
int lst = dep[rep[a]];
auto it = segments[rep[a]].begin();
while(lst <= dep[a]){
nvec.pb(mp(min(dep[a], (*it).fi) - lst + 1, (*it).se));
lst = min(dep[a], (*it).fi) + 1;
it++;
}
a = parent[rep[a]];
reverse(all(nvec));
for(auto ele : nvec){
vec.pb(ele);
}
vector<pii>().swap(nvec);
}
reverse(all(vec));
cout << countInv(vec) << '\n';
vector<pii>().swap(vec);
//upd info
int val = A[b];
while(b != 0){
while(sz(segments[rep[b]]) && (*segments[rep[b]].begin()).fi <= dep[b]){
segments[rep[b]].erase(segments[rep[b]].begin());
}
segments[rep[b]].insert(mp(dep[b], val));
b = parent[rep[b]];
}
// cerr << "========\n";
// for(int i = 1; i <= n; i++){
// cerr << "=== " << i << '\n';
// for(auto ele : segments[i]){
// cerr << ele << '\n';
// }
// }
}
return 0;
}
