#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segTree{
int tree[400002];
int lazy[400002]; /// 즉시 대입
void init(int i, int l, int r){
tree[i] = lazy[i] = 0;
if(l==r) return;
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
}
void propagate(int i, int l, int r){
if(!lazy[i]) return;
if(lazy[i]) tree[i] = lazy[i];
if(l!=r){
lazy[i*2] = lazy[i*2+1] = lazy[i];
}
lazy[i] = 0;
}
void update(int i, int l, int r, int s, int e, int val){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
lazy[i] = val;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i*2, l, m, s, e, val);
update(i*2+1, m+1, r, s, e, val);
}
int getVal(int i, int l, int r, int idx){
propagate(i, l, r);
if(l==r) return tree[i];
int m = (l+r)>>1;
if(idx <= m) return getVal(i*2, l, m, idx);
else return getVal(i*2+1, m+1, r, idx);
}
} tree;
struct Fenwick{
int n;
int arr[100002];
void init(int _n){
n = _n;
fill(arr+1, arr+_n+1, 0);
}
void update(int x, int val){
while(x<=n){
arr[x] += val;
x += x&-x;
}
}
int sum(int x){
int ret = 0;
while(x){
ret += arr[x];
x -= x&-x;
}
return ret;
}
} fenwick;
int n;
int arr[100002];
int par[100002];
int qx[100002], qy[100002];
vector<int> link[100002];
int in[100002], sz[100002], idx[100002], top[100002], depth[100002], inCnt;
int LCADB[100002][20];
void dfs_sz(int x){
LCADB[x][0] = par[x];
sz[x] = 1;
for(auto &y: link[x]){
depth[y] = depth[x] + 1;
dfs_sz(y);
sz[x] += sz[y];
if(sz[y] > sz[link[x][0]]) swap(y, link[x][0]);
}
}
void dfs_hld(int x){
in[x] = ++inCnt;
idx[in[x]] = x;
for(auto y: link[x]){
top[y] = (y == link[x][0]) ? top[x] : y;
dfs_hld(y);
}
}
int kth_parent(int x, int k){
for(int d=0; d<20; d++) if((k>>d)&1) x = LCADB[x][d];
return x;
}
void renumber(){
vector<int> tarr;
for(int i=1; i<=n; i++) tarr.push_back(arr[i]);
sort(tarr.begin(), tarr.end());
tarr.erase(unique(tarr.begin(), tarr.end()), tarr.end());
for(int i=1; i<=n; i++) arr[i] = lower_bound(tarr.begin(), tarr.end(), arr[i]) - tarr.begin() + 1;
}
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d", &arr[i]);
}
renumber();
for(int i=1; i<n; i++){
scanf("%d %d", &qx[i], &qy[i]);
par[qy[i]] = qx[i];
link[qx[i]].push_back(qy[i]);
}
depth[1] = 1;
dfs_sz(1);
top[1] = 1;
dfs_hld(1);
tree.init(1, 1, n);
for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];
for(int i=1; i<=n; i++){
tree.update(1, 1, n, i, i, i);
}
fenwick.init(n);
for(int i=1; i<n; i++){
vector<pair<int, int> > vec;
int x = qx[i];
vec.push_back(make_pair(tree.getVal(1, 1, n, in[x]), depth[x]));
while(x){
if(vec.back().first == tree.getVal(1, 1, n, in[top[x]])){
x = par[top[x]];
continue;
}
int MIN = depth[top[x]], MAX = depth[x], ANS = MIN;
while(MIN <= MAX){
int MID = (MIN + MAX) / 2;
int kth = kth_parent(x, depth[x]-MID);
if(vec.back().first == tree.getVal(1, 1, n, in[kth])){
MAX = MID - 1;
}
else{
ANS = MID;
MIN = MID + 1;
}
}
x = kth_parent(x, depth[x]-ANS);
vec.push_back(make_pair(tree.getVal(1, 1, n, in[x]), depth[x]));
}
for(int i=0; i<(int)vec.size(); i++){
vec[i].first = arr[vec[i].first];
vec[i].second = (i == (int)vec.size()-1) ? vec[i].second : vec[i].second - vec[i+1].second;
}
ll rans = 0;
for(auto p: vec){
rans += ll(p.second) * ll(fenwick.sum(p.first-1));
fenwick.update(p.first, p.second);
}
for(auto p: vec) fenwick.update(p.first, -p.second);
printf("%lld\n", rans);
x = qy[i];
while(x){
tree.update(1, 1, n, in[top[x]], in[x], qy[i]);
x = par[top[x]];
}
}
}
