#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <map>
#include <stack>
using namespace std;
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 200000;
int v[1 + nmax];
int ord[1 + nmax];
map<int,int> mp;
void normalize(int n){
vector<int> temp;
for(int i = 1;i <= n; i++)
temp.push_back(v[i]);
sort(temp.begin(), temp.end());
temp.erase(unique(temp.begin(), temp.end()), temp.end());
for(int i = 0; i < temp.size(); i++)
mp[temp[i]] = 1 + i;
for(int i = 1;i <= n; i++)
v[i] = mp[v[i]];
}
namespace FenwickTree{
vector<int> aib;
int n;
void initialize(int n_){
n = n_;
aib.resize(1 + n);
}
int seen[1 + nmax];
vector<int> touched;
void clean(){
for(int h = 0; h < touched.size(); h++) {
aib[touched[h]] = 0;
seen[touched[h]] = 0;
}
}
void update(int pos, int val){
for(int x = pos; x <= n; x += (x ^ (x & (x - 1)))) {
aib[x] += val;
if(seen[x] == 0) {
touched.push_back(x);
seen[x] = 1;
}
}
}
int query(int pos){
int result = 0;
for(int x = pos; 0 < x; x = (x & (x - 1)))
result += aib[x];
return result;
}
}
namespace HLD{
vector<int> g[1 + nmax];
int far[1 + nmax], sz[1 + nmax];
void dfs(int node){
sz[node] = 1;
for(int h = 0; h < g[node].size(); h++){
int to = g[node][h];
far[to] = node;
dfs(to);
sz[node] += sz[to];
}
}
int ptr = 0;
vector<int> path, path_position;
vector<int> chain_father, chain_size;
stack<pair<int,int>> st[1 + nmax];
void _partition(int node, int curr){
path[node] = curr;
path_position[node] = ++chain_size[curr];
if(path_position[node] == 1)
chain_father[curr] = node;
int best = 0;
for(int h = 0; h < g[node].size(); h++){
int to = g[node][h];
if(sz[best] < sz[to])
best = to;
}
if(0 < best)
_partition(best, curr);
for(int h = 0; h < g[node].size(); h++){
int to = g[node][h];
if(to != best)
_partition(to, ++ptr);
}
}
void intialize(int n){
path.resize(1 + n);
path_position.resize(1 + n);
chain_father.resize(1 + n);
chain_size.resize(1 + n);
ptr = 0;
dfs(1);
_partition(1, ++ptr);
for(int i = 1;i <= ptr; i++)
st[i].push({chain_size[i], 1});
}
vector<pair<int,int>> _affect(int chain, int pos, int val){
vector<pair<int,int>> work;
int last = 0;
while(0 < st[chain].size() && st[chain].top().first <= pos){
work.push_back({st[chain].top().first - last, st[chain].top().second});
last = st[chain].top().first;
st[chain].pop();
}
if(last < pos)
work.push_back({pos - last, st[chain].top().second});
st[chain].push({pos, val});
return work;
}
ll query(int node, int val){
vector<pair<int,int>> work;
int steps = 0;
while(0 < node){
int curr = path[node];
int pos = path_position[node];
vector<pair<int,int>> work2 = _affect(curr, pos, val);
node = far[chain_father[curr]];
reverse(work2.begin(), work2.end());
work.insert(work.end(), work2.begin(), work2.end());
steps++;
if(40 < steps){
while(1);
return 0;
}
}
reverse(work.begin(), work.end());
ll result = 0;
FenwickTree::clean();
for(int i = work.size() - 1; 0 <= i; i--){
result += 1LL * FenwickTree::query(work[i].second - 1) * work[i].first;
FenwickTree::update(work[i].second, work[i].first);
}
return result;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 1;i <= n; i++)
cin >> v[i];
normalize(n);
ord[1] = 1;
for(int i = 2; i <= n; i++) {
int farp;
cin >> farp >> ord[i];
HLD::g[farp].push_back(ord[i]);
}
HLD::intialize(n);
FenwickTree::initialize(n);
for(int i = n;1 <= i; i--)
HLD::query(ord[i], v[ord[i]]);
if(1000 < n)
return 0;
for(int i = 2; i <= n; i++){
int node = ord[i];
cout << HLD::query(HLD::far[node], v[node]) << '\n';
}
return 0;
}
/*
10
1 100 3 4 8 6 2 9 10 0
1 2
1 3
2 4
3 5
2 6
3 7
4 8
5 9
6 10
*/
