#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
typedef long long ll;
int n;
namespace sub12{
void solve(){
vector<int>c(n + 1), _c(n);
for(int i = 1; i <= n; i++){
cin >> c[i];
_c[i - 1] = c[i];
}
sort(_c.begin(), _c.end());
for(int i = 1; i <= n; i++){
c[i] = lower_bound(_c.begin(), _c.end(), c[i]) - _c.begin() + 1;
}
vector<int>bit(n + 1);
auto update = [&] (int p){
for(; p <= n; p += p & -p){
bit[p]++;
}
};
auto get = [&] (int p){
int ans = 0;
for(; p > 0; p -= p & -p){
ans += bit[p];
}
return ans;
};
int a, b, ans;
vector<vector<int>>g(n + 1);
vector<int>path;
function<void(int, int)>dfs;
dfs = [&] (int s, int p){
path.emplace_back(s);
for(int& d : g[s]){
if(d != p){
dfs(d, s);
}
}
if(s == a){
for(int i = int(path.size()) - 1; i > -1; i--){
ans += get(c[path[i]] - 1);
update(c[path[i]]);
}
for(int& i : path){
c[i] = c[b];
}
}
path.pop_back();
};
for(int _ = 1; _ < n; _++){
cin >> a >> b;
fill(bit.begin(), bit.end(), ans = 0);
dfs(1, -1);
cout << ans << "\n";
g[a].emplace_back(b);
g[b].emplace_back(a);
}
}
}
namespace sub3{
const int lim = 1e5 + 5;
vector<int>g[lim];
int parent[lim], c[lim], cnt_child[lim], head[lim], h[lim], bit[lim];
stack<tuple<int, int, int>>chain[lim];
void dfs(int s){
cnt_child[s] = 1;
for(int& d : g[s]){
h[d] = h[parent[d] = s] + 1;
dfs(d);
cnt_child[s] += cnt_child[d];
}
}
void hld(int s){
if(!g[s].empty()){
int heavy = g[s][0];
for(int& d : g[s]){
if(cnt_child[d] > cnt_child[heavy]){
heavy = d;
}
}
head[heavy] = head[s];
hld(heavy);
for(int& d : g[s]){
if(d != heavy){
hld(head[d] = d);
}
}
}
chain[head[s]].emplace(h[s], h[s], c[s]);
}
void update(int p, int x){
for(; p <= n; p += p & -p){
bit[p] += x;
}
}
int get(int p){
int ans = 0;
for(; p > 0; p -= p & -p){
ans += bit[p];
}
return ans;
}
void solve(){
vector<int>_c;
for(int i = 1; i <= n; i++){
cin >> c[i];
_c.emplace_back(c[i]);
}
sort(_c.begin(), _c.end());
for(int i = 1; i <= n; i++){
c[i] = lower_bound(_c.begin(), _c.end(), c[i]) - _c.begin() + 1;
}
vector<pair<int, int>>query(n - 1);
for(auto& [u, v] : query){
cin >> u >> v;
g[u].emplace_back(v);
}
dfs(h[1] = 1);
hld(head[1] = 1);
memset(bit, parent[1] = 0, sizeof(bit));
for(auto& [u, v] : query){
vector<pair<int, int>>a;
int temp = c[v];
while(u != 0){
vector<pair<int, int>>ve;
while(true){
auto& [h_up, h_down, color] = chain[head[u]].top();
chain[head[u]].pop();
if(h_down >= h[u]){
ve.emplace_back(h[u] - h_up + 1, color);
if(h_down > h[u]){
chain[head[u]].emplace(h[u] + 1, h_down, color);
}
chain[head[u]].emplace(h[head[u]], h[u], temp);
break;
}
ve.emplace_back(h_down - h_up + 1, color);
}
for(int i = ve.size(); i > 0; ){
a.emplace_back(ve[--i]);
}
u = parent[head[u]];
}
ll ans = 0;
for(auto& [len, color] : a){
ans += get(color - 1);
update(color, len);
}
cout << ans << "\n";
for(auto& [len, color] : a){
update(color, -len);
}
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n;
if(n <= 4000){
sub12::solve();
}
else{
sub3::solve();
}
}
