// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
#define f first
#define s second
#define mp make_pair
#define sz(x) int(x.size())
using pi = pair<int, int>;
using ll = long long;
template<class T> using V = vector<T>;
using vi = V<int>;
using vpi = V<pi>;
const int LG = 18;
struct BIT {
vi data; int N; void init(int n) { N = n; data = vi(N, 0); }
void add(int p, int x) { for(++p; p <= N; p += p & -p) data[p - 1] += x; }
int sum(int l, int r) { return sum(r + 1) - sum(l); }
int sum(int r) { int s = 0; for(; r; r -= r & -r) s += data[r - 1]; return s; }
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int N; cin >> N;
vi A(N); for(auto& x : A) cin >> x;
{
vi C = A; sort(begin(C), end(C));
for(auto& x : A) x = lower_bound(begin(C), end(C), x) - begin(C);
}
V<vi> adj(N);
vi Q(N-1);
for(int i = 0; i < N-1; i++) {
int u, v; cin >> u >> v; --u, --v;
adj[u].pb(v);
Q[i] = v;
}
vi nxt(N), par(N), dep(N, 0), siz(N); V<vpi> st(N);
function<void(int)> gen = [&](int u) {
for(auto& v : adj[u]) {
dep[v] = dep[u] + 1;
par[v] = u;
gen(v);
siz[u] += siz[v];
}
};
function<void(int, int)> dfs = [&](int u, int h) {
nxt[u] = h;
int hvy = -1;
for(auto& v : adj[u]) {
if (hvy == -1 || siz[hvy] < siz[v]) hvy = v;
}
if (hvy == -1) return;
dfs(hvy, h);
for(auto& v : adj[u]) if (v != hvy) dfs(v, v);
};
gen(0);
par[0] = -1; dfs(0, 0);
BIT B; B.init(N);
auto answer = [&](vpi &X) {
ll ans = 0;
for(auto& x : X) {
// cout << x.f << " => " << x.s << endl;
ans += x.s * 1LL * B.sum(x.f);
B.add(x.f, x.s);
}
for(auto& x : X) B.add(x.f, -x.s);
cout << ans << nl;
};
for(auto u : Q) {
vpi X; int c = A[u];
while(u != -1) {
// cout << "U: " << u << endl;
int d = dep[u]; vpi R;
u = nxt[u]; int t = dep[u] - 1; // cout << "C: " << u << endl;
while(sz(st[u]) && st[u].back().s <= d) {
pi bk = st[u].back(); // cout << bk.f << " -> " << bk.s << endl;
R.pb(mp(bk.f, bk.s - t)); t = bk.s;
st[u].pop_back();
}
if (sz(st[u])) R.pb(mp(st[u].back().f, d - t));
st[u].pb(mp(c, d));
reverse(begin(R), end(R));
X.insert(end(X), begin(R), end(R));
u = par[u];
}
answer(X);
// cout << endl << endl << endl;
}
exit(0-0);
}
