#include <bits/stdc++.h> using namespace std; #define NAME "A" #define ll long long #define fi first #define se second #define pb push_back #define all(x) x.begin(), x.end() #define MASK(x) (1ll << (x)) #define BIT(x, i) (((x) >> (i)) & 1) const int N = 1e5 + 5; struct FenwickTree { int n; vector<int> fen; FenwickTree() {} FenwickTree(int n): n(n), fen(n + 1) {} void update(int x, int v) { for (int i = x; i <= n; i += i & -i) { fen[i] += v; } } int get(int x) { int res = 0; for (int i = x; i > 0; i -= i & -i) { res += fen[i]; } return res; } }; int n; int a[N], p[N], sz[N], head[N], hi[N]; vector<int> vals, g[N]; vector<pair<int, int>> edge, s[N]; FenwickTree fen; void dfs(int u, int par) { sz[u] = 1; p[u] = par; hi[u] = hi[par] + 1; for (int v : g[u]) { if (v == par) continue; dfs(v, u); sz[u] += sz[v]; } } void hld(int u, int par, int he) { head[u] = he; int beo = 0; for (int v : g[u]) { if (v == par) continue; if (sz[v] > sz[beo]) { beo = v; } } if (beo) { hld(beo, u, he); } for (int v : g[u]) { if (v != par && v != beo) { hld(v, u, v); } } } void update(int u, int val) { while (u) { int h = head[u]; int d = hi[u] - hi[head[u]] + 1; while (s[h].size() && s[h].back().fi <= d) { s[h].pop_back(); } s[h].pb({d, val}); u = p[h]; } } ll get(int u) { ll ans = 0; vector<pair<int, int>> vec; while (u) { int h = head[u]; int d = hi[u] - hi[head[u]] + 1; int last = 0; vector<pair<int, int>> cur; for (int i = s[h].size() - 1; i >= 0; i--) { int x = s[h][i].fi, val = s[h][i].se; cur.pb({min(x, d) - last, val}); last = x; if (x >= d) break; } for (int i = cur.size() - 1; i >= 0; i--) { vec.pb(cur[i]); } u = p[h]; } for (auto it : vec) { ans += 1ll * it.fi * fen.get(it.se - 1); fen.update(it.se, it.fi); } for (auto it : vec) { fen.update(it.se, -it.fi); } return ans; } void input() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; vals.pb(a[i]); } sort(all(vals)); vals.erase(unique(all(vals)), vals.end()); for (int i = 1; i <= n; i++) { a[i] = upper_bound(all(vals), a[i]) - vals.begin(); } fen = FenwickTree(vals.size()); for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; g[u].pb(v); g[v].pb(u); edge.pb({u, v}); } } void solve() { dfs(1, 0); hld(1, 0, 1); for (auto it : edge) { int u = it.fi, v = it.se; cout << get(u) << "\n"; update(v, a[v]); } } signed main() { if (fopen(NAME".INP", "r")) { freopen(NAME".INP", "r", stdin); freopen(NAME".OUT", "w", stdout); } cin.tie(0)->sync_with_stdio(0); input(); solve(); return 0; }

construction.cpp: In function 'int main()':
construction.cpp:148:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |         freopen(NAME".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:149:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         freopen(NAME".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~