#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; const int tree_siz = 1024*256-1; ll sum[tree_siz+1]; ll get_sum(int akt, int p1, int p2, int s1, int s2) { if(p2 < s1 || p1 > s2) return 0; if(p1 >= s1 && p2 <= s2) return sum[akt]; return get_sum(akt*2,p1,(p1+p2)/2,s1,s2)+get_sum(akt*2+1,(p1+p2)/2+1,p2,s1,s2); } void upd(int v) { sum[v] = sum[v*2]+sum[v*2+1]; if(v != 1) upd(v/2); } void change(int ind, int val) { sum[tree_siz/2+ind+1] += val; upd((tree_siz/2+1+ind)/2); } vi graph[100001]; int val[100001]; int path[100001]; int path_end[100001]; stack<pii> path_events[100001]; int P[100001]; int pre[100001]; int maxpre[100001]; int siz_[100001]; int depth[100001]; int cur_pre; int cur_path; void dfs_siz(int v, int d = 0) { siz_[v] = 1; pre[v] = cur_pre++; maxpre[v] = pre[v]; depth[v] = d++; forall(it,graph[v]) { dfs_siz(it,d); siz_[v] += siz_[it]; maxpre[v] = maxpre[it]; } } void dfs_HLD(int v, int p) { path[v] = p; pii best = {-1e9,-1}; forall(it,graph[v]) best = max(best,{siz_[it],it}); if(best.ss != -1) { dfs_HLD(best.ss,p); } forall(it,graph[v]) if(it != best.ss) { path_end[cur_path] = it; dfs_HLD(it,cur_path++); } } ll count_inv(vector<pii>& T) { ll ans = 0; forall(it,T) { ans += get_sum(1,0,tree_siz/2,it.ff+1,tree_siz/2)*(ll)it.ss; change(it.ff,it.ss); } forall(it,T) change(it.ff,-it.ss); return ans; } vector<pii> pom; void query(int v) { int v2 = v; v = P[v]; vector<pii> ans; int cnt = 0; while(v != 0) { int pop = P[path_end[path[v]]]; while(!path_events[path[v]].empty()) { if(depth[v] > depth[path_events[path[v]].top().ss]) { pom.pb({path_events[path[v]].top().ff,depth[path_events[path[v]].top().ss]-depth[pop]}); pop = path_events[path[v]].top().ss; path_events[path[v]].pop(); } else { pom.pb({path_events[path[v]].top().ff,depth[v]-depth[pop]}); if(depth[v] == depth[path_events[path[v]].top().ss]) path_events[path[v]].pop(); break; } } if(cnt != 0) path_events[path[v]].push({val[v2],v}); else { if(path[v] == path[v2]) path_events[path[v]].push({val[v2],v2}); else { path_events[path[v]].push({val[v2],v}); path_events[path[v2]].push({val[v2],v2}); } } reverse(all(pom)); forall(it,pom) ans.pb(it); pom = {}; v = P[path_end[path[v]]]; cnt++; } reverse(all(ans)); cout << count_inv(ans) << "\n"; } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random_start(); int n; cin >> n; map<int,int> m; rep2(i,1,n) cin >> val[i]; rep2(i,1,n) m[val[i]] = 1; int cur = 1; forall(it,m) m[it.ff] = cur++; rep2(i,1,n) val[i] = m[val[i]]; vi q = {}; P[1] = 0; rep(i,n-1) { int a,b; cin >> a >> b; graph[a].pb(b); P[b] = a; q.pb(b); } depth[0] = -1; dfs_siz(1); cur_path = 1; path_end[0] = 1; dfs_HLD(1,0); path_events[0].push({val[1],1}); forall(it,q) query(it); }