#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll #define ft first #define sc second #define pb push_back #define all(x) x.begin(), x.end() #define pi pair<int, int> #define vi vector<int> #define tii tuple<int, int, int> #define tiii tuple<int, int, int, int> #define tiiii tuple<int, int, int, int, int> #define vpi vector<pi> #define vtii vector<tii> #define vtiii vector<tiii> const int N = (1 << 20), MOD = 1e9 + 7, INF = int(1e18); int p[N], w[N], d[N]; vi graf[N]; struct treep{ int t[2 * N]; vi z; void upd(int x, int v){ z.pb(x); x += N; t[x] = v; do{ x /= 2; t[x] = t[2 * x] + t[2 * x + 1]; }while(x > 1); } int que(int l, int r){ if(r < l) return 0; l += N - 1; r += N + 1; int ans = 0; while(l / 2 != r / 2){ if(l % 2 == 0) ans += t[l + 1]; if(r % 2 == 1) ans += t[r - 1]; l /= 2; r /= 2; } return ans; } void clr(){ while(!z.empty()){ upd(z.back(), 0); z.pop_back(); z.pop_back(); } } }; struct trees{ pi t[2 * N]; int cz = 0; void upd(int l, int r, int x){ cz++; l += N - 1; r += N + 1; while(l / 2 != r / 2){ if(l % 2 == 0) t[l + 1] = {x, cz}; if(r % 2 == 1) t[r - 1] = {x, cz}; l /= 2; r /= 2; } } int que(int x){ x += N; pi ans = {-1, -1}; while(x >= 1){ if(t[x].sc > ans.sc) ans = t[x]; x /= 2; } return ans.ft; } }; treep tri; trees hld; int idx[N], sz[N]; void dfs(int u, int v){ p[u] = v; d[u] = d[v] + 1; sz[u] = 1; for(auto i : graf[u]){ if(i == v) continue; dfs(i, u); sz[u] += sz[i]; } } int hr[N]; void dfs2(int u, int v, int &t){ idx[u] = ++t; int mx = -1; for(auto i : graf[u]){ if(i == v) continue; if(sz[i] > sz[mx]) mx = i; } if(mx == -1) return; hr[mx] = hr[u]; dfs2(mx, u, t); for(auto i : graf[u]){ if(i == v || i == mx) continue; hr[i] = i; dfs2(i, u, t); } } int f[N], l[N]; int get_col(int x){ return hld.que(idx[x]); } void upd_col(int x){ int c = x; hld.upd(idx[x], idx[x], x); while(x > 1){ int a = hr[x]; if(a == p[x]) hld.upd(idx[a], idx[a], c); else hld.upd(idx[a], idx[x], c); x = a; } } int add(int x){ int org = x; int akt = get_col(p[x]), lst = p[x], c = akt; int ans = 0; do{ akt = f[akt]; f[c] = l[lst]; if(lst != x) l[lst] = x; int dl = d[lst] - d[akt] + 1; ans += dl * tri.que(1, w[c] - 1); tri.upd(w[c], dl); lst = p[akt]; x = akt; c = get_col(lst); akt = c; }while(x != 1); upd_col(org); tri.clr(); f[org] = 1; l[p[org]] = org; return ans; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); // random_device rd; // mt19937_64 gen(rd()); int n; cin >> n; vpi v; for(int i = 1; i <= n; i++){ int a; cin >> a; v.pb({a, i}); } sort(all(v)); for(int i = 0; i < n; i++){ auto [a, b] = v[i]; if(i == 0 || a != v[i - 1].ft) w[b] = i + 1; else w[b] = w[v[i - 1].sc]; } vpi z; for(int i = 1; i < n; i++){ int a, b; cin >> a >> b; z.pb({a, b}); graf[a].pb(b); graf[b].pb(a); } f[1] = hr[1] = 1; int t = 0; dfs(1, 1); dfs2(1, 1, t); hld.upd(1, 1, 1); for(int i = 1; i <= n; i++){ if(hr[i] == i) hr[i] = p[i]; } for(auto i : z) cout << add(i.sc) << "\n"; return 0; }