#include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; const int N = 1<<17; vector<int> nei[N]; vector<pair<int, int>> vec[N]; int ft[N], cl[N], tp[N], ch[N], Par[N], hei[N], a[N], b[N]; map<int, int> mp, mp2; void Add(int i, int v){ for (; i < N; i += i & -i) ft[i] += v; } int get(int i, int ans = 0){ for (; i ; i -= i & -i) ans += ft[i]; return ans; } void dfs(int u,int id = 0){ ch[u] = 1; for (int i : nei[u]){ Par[i] = u, hei[i] = hei[u] + 1; dfs(i); ch[u] += ch[i]; if (ch[i] > ch[nei[u][0]]) swap(nei[u][id], nei[u][0]); tp[i] = i; id++; } } void dfs2(int u){ if (nei[u].size() > 0) tp[nei[u][0]] = tp[u]; for (int i : nei[u]) dfs2(i); } int clac_and_upd(int u, int vr){ vector<pair<int, int>> temp, Now; while (u){ int t = tp[u], sz2 = hei[u] - hei[t] + 1, sz = sz2, k = 0; while (sz){ if (vec[t].back().second > sz){ temp.push_back({vec[t].back().first, sz}); vec[t].back().second -= sz; sz = 0; } else{ sz -= vec[t].back().second; temp.push_back(vec[t].back()); vec[t].pop_back(); } } vec[t].push_back({cl[vr], sz2 + (tp[vr] == t)}); u = Par[t]; for (int i=temp.size()-1; i >= 0;i--) Now.push_back(temp[i]); vector<pair<int,int>> ().swap(temp); } long long Ans = 0; for (auto [c, cnt] : Now){ Ans += 1LL * get(c-1) * cnt; Add(c, cnt); } for (auto [c, cnt] : Now) Add(c, -cnt); return Ans; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, cur = 0; cin>>n; for (int i=1;i<=n;i++) cin>>cl[i], mp[cl[i]]; for (auto [i, j] : mp) mp2[i] = ++cur; for (int i=1;i<=n;i++) cl[i] = mp2[cl[i]]; for (int i=1;i<n;i++){ cin>>a[i]>>b[i]; nei[a[i]].push_back(b[i]); } dfs(1); dfs2(tp[1] = 1); vec[1].push_back({cl[1], 1}); for (int i=1;i<n;i++){ cout<<clac_and_upd(a[i], b[i])<<endl; if (tp[b[i]] == b[i]) vec[b[i]].push_back({cl[b[i]], 1}); } }