#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; --i)
#define FORLL(i, a, b) for (ll i = a, _b = b; i <= _b; ++i)
#define FORDLL(i, a, b) for (ll i = a, _b = b; i >= _b; --i)
#define all(x) x.begin(), x.end()
#define uni(x) sort(all(x)), x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__)
template<typename T>
void __print_one(const char *&s, const T &x)
{
while (*s == ' ') ++s;
const char *p = s;
int bal = 0;
while (*s)
{
if (*s == '(') ++bal;
else if (*s == ')') --bal;
else if (*s == ',' && bal == 0) break;
++s;
}
cerr.write(p, s - p) << " = " << x;
if (*s == ',')
{
++s;
cerr << " , ";
}
}
template<typename... Args>
void debug(const char *s, Args... args)
{
cerr << "[ ";
int dummy[] = { 0 , ( __print_one(s, args) , 0 )... };
(void)dummy;
cerr << " ]\n\n";
}
template<class X>
bool maximize(X &a, X b)
{
if (a < b)
{
a = b;
return true;
}
return false;
}
template<class X>
bool minimize(X &a, X b)
{
if (a > b)
{
a = b;
return true;
}
return false;
}
// --------------------------------------------------------------------------------------------
const int maxn = 1e5 + 3;
int n, a[maxn];
vector<int> ids;
struct FenTree
{
vector<ll> fw;
void init(int n)
{
fw.assign(n + 3, 0ll);
}
void upd(int pos, ll val)
{
for (; pos < (int)fw.size(); pos += pos & -pos)
fw[pos] += val;
}
ll get(int pos)
{
ll res = 0;
for (; pos; pos &= pos - 1)
res += fw[pos];
return res;
}
void reset(int pos)
{
for (; pos < (int)fw.size(); pos += pos & -pos)
fw[pos] = 0;
}
};
// --------------------------------------------------------------------------------------------
namespace sub12
{
int par[maxn];
FenTree fw;
ll calc(int root)
{
ll res = 0;
int ver = par[root];
while (ver)
{
res += fw.get(a[ver] - 1);
fw.upd(a[ver], 1);
ver = par[ver];
}
ver = par[root];
while (ver)
{
fw.upd(a[ver], -1);
a[ver] = a[root];
ver = par[ver];
}
return res;
}
void solve()
{
fw.init(n);
FOR(im, 2, n)
{
int u, v; cin >> u >> v;
par[v] = u;
cout << calc(v) << '\n';
}
}
}
namespace AC
{
FenTree fw;
struct Block
{
int l, r, val;
Block() {}
Block(int l, int r, int val) : l(l), r(r), val(val) {}
bool operator < (const Block &other) const
{
return l < other.l;
}
};
set<Block> S;
int tin[maxn], tdfs, sz[maxn], hv[maxn], root, par[maxn], head[maxn], tour[maxn];
vector<pii> eds;
vector<int> g[maxn];
void dfs_pre(int u, int p)
{
sz[u] = 1;
for (int v : g[u])
{
if (v == p) continue;
par[v] = u;
dfs_pre(v, u);
sz[u] += sz[v];
if (sz[v] > sz[hv[u]]) hv[u] = v;
}
}
void hld(int u)
{
head[u] = root;
tin[u] = ++tdfs;
tour[tdfs] = u;
if (!hv[u]) return;
hld(hv[u]);
for (int v : g[u])
{
if (v == par[u] || v == hv[u]) continue;
root = v;
hld(v);
}
}
auto split(int k)
{
auto it = prev(S.upper_bound(Block(k, -1e9, -1e9)));
if (it->r > k)
{
Block bLeft = Block(it->l, k, it->val), bRight = Block(k + 1, it->r, it->val);
S.erase(it);
S.insert(bRight);
return S.insert(bLeft).fi;
}
return it;
}
void DBG()
{
for (const auto &e : S)
cerr << e.l << ' ' << e.r << ' ' << e.val << " ";
cerr << endl << endl;
}
// split, interate, merge
ll getHld(int u, int val)
{
static int CNT = 0;
++CNT;
// dbg(CNT);
// DBG();
ll res = 0;
vector<int> delVal;
vector<Block> addBlock;
while (head[u])
{
split(tin[u]);
auto it = S.upper_bound(Block(tin[u], -1e9, -1e9));
auto itL = it;
while (itL != S.begin() && prev(itL)->l >= tin[head[u]])
{
--itL;
ll len = itL->r - itL->l + 1;
res += fw.get(itL->val - 1) * len;
// dbg(itL->l, itL->r, fw.get(itL->val - 1), len, res);
fw.upd(itL->val, len);
delVal.push_back(itL->val);
}
if (itL != it)
{
addBlock.push_back(Block(itL->l, prev(it)->r, val));
S.erase(itL, it);
}
// dbg(itL->l, it->l);
if (head[u] == 1)
break;
u = par[head[u]];
}
for (int x : delVal)
fw.reset(x);
for (const Block &b : addBlock)
{
auto it = S.insert(b).fi;
auto nx = next(it);
if (nx != S.end() && head[tour[nx->l]] == head[tour[it->l]] && it->val == nx->val)
{
Block newBlock = Block(it->l, nx->r, it->val);
S.erase(it, next(nx));
S.insert(newBlock);
}
}
// DBG();
return res;
}
void solve()
{
fw.init(n);
FOR(i, 2, n)
{
int u, v; cin >> u >> v;
eds.push_back({u, v});
g[u].push_back(v);
g[v].push_back(u);
}
dfs_pre(1, -1);
root = 1;
hld(1);
FOR(i, 1, n)
{
S.insert(Block(tin[i], tin[i], a[i]));
}
FOR(id, 1, n - 1)
{
int u, v; tie(u, v) = eds[id - 1];
cout << getHld(u, a[v]) << '\n';
}
}
}
void solve()
{
cin >> n;
ids.push_back(-2e9);
FOR(i, 1, n)
{
cin >> a[i];
ids.push_back(a[i]);
}
uni(ids);
FOR(i, 1, n)
a[i] = lower_bound(all(ids), a[i]) - ids.begin();
if (n <= 4000) sub12 :: solve();
else AC :: solve();
}
signed main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define TASK "TEST"
if (fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
freopen(TASK".OUT", "w", stdout);
}
solve();
return 0;
}
