#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
const int inf = 1e9 + 7;
int n, MAX;
int a[maxn];
vector<int> g[maxn];
vector<pair<int, int>> edges;
void compress()
{
unordered_map<int, int> compressedValues;
int curr = 0;
vector<int> toCompress;
for (int i = 1; i <= n; ++i)
{
toCompress.push_back(a[i]);
}
sort(toCompress.begin(), toCompress.end());
for (int i = 0; i < n; ++i)
{
if (i == 0 || toCompress[i] != toCompress[i - 1])
{
compressedValues[toCompress[i]] = ++curr;
}
}
MAX = curr;
for (int i = 1; i <= n; ++i)
{
a[i] = compressedValues[a[i]];
}
}
long long answer = 0;
struct FenwickTree
{
int tree[maxn];
void update(int pos, int add)
{
for (; pos <= MAX; pos += (pos & (-pos)))
{
tree[pos] += add;
}
}
int query(int pos)
{
int result = 0;
for (; pos >= 1; pos -= (pos & (-pos)))
{
result += tree[pos];
}
return result;
}
};
FenwickTree bit;
vector<pair<int, int>> toClear;
struct Node
{
int maxv, minv;
inline friend Node operator + (const Node& lf, const Node& rf)
{
return {max(lf.maxv, rf.maxv), min(lf.minv, rf.minv)};
}
};
struct SegmentTreeBeats
{
Node tree[4 * maxn];
int lazy[4 * maxn];
void init(int node, int l, int r)
{
lazy[node] = -1;
if (l == r)
{
tree[node].maxv = 0;
tree[node].minv = inf;
return;
}
int mid = (l + r) / 2;
init(2 * node, l, mid);
init(2 * node + 1, mid + 1, r);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
void updatePoint(int node, int l, int r, int pos, int value)
{
if (l == r)
{
tree[node].minv = tree[node].maxv = value;
return;
}
int mid = (l + r) / 2;
if (pos <= mid)
{
updatePoint(2 * node, l, mid, pos, value);
}
else
{
updatePoint(2 * node + 1, mid + 1, r, pos, value);
}
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
void pushLazy(int node, int l, int r)
{
if (lazy[node] == -1) return;
tree[node].minv = tree[node].maxv = lazy[node];
if (l != r)
{
lazy[2 * node] = lazy[node];
lazy[2 * node + 1] = lazy[node];
}
lazy[node] = -1;
}
void updateRange(int node, int l, int r, int ql, int qr, int value)
{
pushLazy(node, l, r);
if (l > qr || r < ql) return;
if (ql <= l && r <= qr)
{
lazy[node] = value;
pushLazy(node, l, r);
return;
}
int mid = (l + r) / 2;
updateRange(2 * node, l, mid, ql, qr, value);
updateRange(2 * node + 1, mid + 1, r, ql, qr, value);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
void query(int node, int l, int r, int ql, int qr)
{
pushLazy(node, l, r);
if (l > qr || r < ql) return;
if (ql <= l && r <= qr && tree[node].maxv == tree[node].minv)
{
answer += (1LL * (r - l + 1)) * (1LL * bit.query(tree[node].maxv - 1));
bit.update(tree[node].maxv, r - l + 1);
toClear.push_back({tree[node].maxv, r - l + 1});
return;
}
int mid = (l + r) / 2;
query(2 * node + 1, mid + 1, r, ql, qr);
query(2 * node, l, mid, ql, qr);
}
};
SegmentTreeBeats tree;
int parent[maxn], head[maxn], heavy[maxn], subtreeSize[maxn], depth[maxn], posHld[maxn];
int currPos = 1;
void dfs1(int node, int par, int dep)
{
parent[node] = par;
depth[node] = dep;
subtreeSize[node] = 1;
int maxSize = -1;
heavy[node] = -1;
for (auto to : g[node])
{
if (to != par)
{
dfs1(to, node, dep + 1);
subtreeSize[node] += subtreeSize[to];
if (maxSize < subtreeSize[to])
{
maxSize = subtreeSize[to];
heavy[node] = to;
}
}
}
}
void decompose(int node, int currHead)
{
head[node] = currHead;
posHld[node] = currPos++;
if (heavy[node] != -1)
{
decompose(heavy[node], currHead);
}
for (auto to : g[node])
{
if (to != parent[node] && to != heavy[node])
{
decompose(to, to);
}
}
}
long long path(int x, int y, int newValue)
{
answer = 0;
toClear.clear();
while (head[x] != head[y])
{
if (depth[head[x]] < depth[head[y]])
{
swap(x, y);
}
tree.query(1, 1, n, posHld[head[x]], posHld[x]);
tree.updateRange(1, 1, n, posHld[head[x]], posHld[x], newValue);
x = parent[head[x]];
}
if (depth[x] > depth[y])
{
swap(x, y);
}
tree.query(1, 1, n, posHld[x], posHld[y]);
tree.updateRange(1, 1, n, posHld[x], posHld[y], newValue);
for (auto [pos, value] : toClear)
{
bit.update(pos, -value);
}
return answer;
}
void fastIO()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
{
fastIO();
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
for (int i = 1; i < n; ++i)
{
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
edges.push_back({x, y});
}
compress();
dfs1(1, 1, 1);
decompose(1, 1);
tree.init(1, 1, n);
for (int i = 1; i <= n; ++i)
{
tree.updatePoint(1, 1, n, posHld[i], a[i]);
}
for (auto [x, y] : edges)
{
cout << path(1, x, a[y]) << "\n";
}
return 0;
}
