#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define FordE(i, l, r) for (int i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;
const int N = 1e5 + 5, mod = 1e9 + 7;
struct lazy_segment_tree_sum{
int seg[1 << 18], lazy[1 << 18];
void down(int id){
if (lazy[id]){
seg[id * 2] = seg[id * 2 + 1] = 0;
lazy[id * 2] = lazy[id * 2 + 1] = 1;
lazy[id] = 0;
}
}
void reset(){
lazy[1] = 1;
}
void update(int id, int l, int r, int i, int val){
if (l == r){
seg[id] += val;
return;
}
down(id);
int mid = (l + r) >> 1;
if (i <= mid){
update(id * 2, l, mid, i, val);
}
else{
update(id * 2 + 1, mid + 1, r, i, val);
}
seg[id] = seg[id * 2] + seg[id * 2 + 1];
}
int get(int id, int l, int r, int u, int v){
if (v < l or r < u){
return 0;
}
if (u <= l and r <= v){
return seg[id];
}
down(id);
int mid = (l + r) >> 1;
return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
}
} segval;
struct lazy_chain{
struct node{
int val, chainbegin, chainend, child;
node(){
}
node(int val, int chainbegin, int chainend, int child = 0): val(val), chainbegin(chainbegin), chainend(chainend), child(child){
}
};
node seg[1 << 18];
void build(int id, int l, int r, int aval[]){
if (l == r){
seg[id] = node(aval[tour[l]], tour[l], tour[l]);
return;
}
int mid = (l + r) >> 1;
build(id * 2, l, mid, aval);
build(id * 2 + 1, mid + 1, r, aval);
}
node getnode(int id, int l, int r, int i){
if (l == r){
return seg[id];
}
int mid = (l + r) >> 1;
if (i <= mid){
return getnode(id * 2, l, mid);
}
else{
return getnode(id * 2 + 1, mid + 1, r);
}
}
} segchain;
int n;
int a[N];
pii aquery[N];
vi adj[N];
int par[N];
int h[N], sz[N];
int ctrtour, tour[N], tin[N], tout[N];
int nxt[N];
void dfs_sz(int u){
sz[u] = 1;
Fora(&v, adj[u]){
h[v] = h[u] + 1;
dfs_sz(v);
sz[u] += sz[v];
if (sz[v] > sz[adj[u][0]]){
swap(v, adj[u][0]);
}
}
}
void dfs_tour(int u){
tour[++ctrtour] = u;
tin[u] = ctrtour;
Fora(v, adj[u]){
nxt[v] = (v == adj[u][0] ? nxt[u] : v);
dfs_tour(v);
}
tout[u] = ctrtour;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("KEK.inp", "r", stdin);
// freopen("KEK.out", "w", stdout);
cin >> n;
ForE(i, 1, n){
cin >> a[i];
}
For(i, 1, n){
cin >> aquery[i].fi >> aquery[i].se;
}
{
int ctrmpp = 0; map <int, int> mpp;
ForE(i, 1, n){
mpp[a[i]] = 1;
}
Fora(&elem, mpp){
elem.se = ++ctrmpp;
}
ForE(i, 1, n){
a[i] = mpp[a[i]];
}
}
{
For(i, 1, n){
adj[aquery[i].fi].emplace_back(aquery[i].se);
par[aquery[i].se] = aquery[i].fi;
}
dfs_sz(1);
nxt[1] = 1;
dfs_tour(1);
}
segchain.build(1, 1, n, a);
For(i, 1, n){
int u = aquery[i].fi, v = aquery[i].se;
{
ll ans = 0;
segval.reset();
while (u){
auto nodeu = segchain.getnode(1, 1, n, tin[u]);
ans += (ll)segval.get(1, 1, n, 1, nodeu.val - 1) * (h[u] - h[nodeu.chainbegin] + 1);
segval.update(1, 1, n, nodeu.val, h[u] - h[nodeu.chainbegin] + 1);
u = par[nodeu.chainbegin];
}
cout << ans << endl;
}
u = aquery[i].fi;
{
while (u){
auto nodeu = segchain.getnode(1, 1, n, tin[u]);
}
}
}
}
/*
==================================================+
INPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
Compilation message
construction.cpp: In member function 'void lazy_chain::build(int, int, int, int*)':
construction.cpp:87:33: error: 'tour' was not declared in this scope
87 | seg[id] = node(aval[tour[l]], tour[l], tour[l]);
| ^~~~
construction.cpp: In member function 'lazy_chain::node lazy_chain::getnode(int, int, int, int)':
construction.cpp:101:42: error: no matching function for call to 'lazy_chain::getnode(int, int&, int&)'
101 | return getnode(id * 2, l, mid);
| ^
construction.cpp:95:10: note: candidate: 'lazy_chain::node lazy_chain::getnode(int, int, int, int)'
95 | node getnode(int id, int l, int r, int i){
| ^~~~~~~
construction.cpp:95:10: note: candidate expects 4 arguments, 3 provided
construction.cpp:104:50: error: no matching function for call to 'lazy_chain::getnode(int, int, int&)'
104 | return getnode(id * 2 + 1, mid + 1, r);
| ^
construction.cpp:95:10: note: candidate: 'lazy_chain::node lazy_chain::getnode(int, int, int, int)'
95 | node getnode(int id, int l, int r, int i){
| ^~~~~~~
construction.cpp:95:10: note: candidate expects 4 arguments, 3 provided
construction.cpp: In function 'int main()':
construction.cpp:178:31: warning: unused variable 'v' [-Wunused-variable]
178 | int u = aquery[i].fi, v = aquery[i].se;
| ^
