#include <bits/stdc++.h> #pragma GCC target ("avx2") #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") using namespace std; #define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define Int __int128 //#define int long long #define ll long long #define dl double long #define fl float #define all(s) s.begin(), s.end() #define lall(s) ++s.begin(), s.end() #define pub push_back #define puf push_front #define pob pop_back #define pof pop_front #define ins insert #define F first #define S second const int N = 100000 + 5; const int M = 1000 + 5; const int LN = 131072; const int MOD = 1e9 + 7;//998244353; const int BLOCK = 500; const int inf = 1e9; const int INF = 1e18; const double pi = 3.14159265358979323846; const vector<array<int, 2>> DS {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int binpow(int a, int b) {//, int MOD) { int res = 1; a %= MOD; while (b > 0) { if (b & 1) { res = res * a; res %= MOD; } a = a * a; a %= MOD; b >>= 1; } return res; } int mdiv(int a, int b) { int ret = (a % MOD) * binpow(b, MOD - 2); ret %= MOD; return ret; } int mul(int a, int b) { int ret = (a % MOD) * (b % MOD); ret %= MOD; return ret; } int add(int a, int b) { int ret = (a % MOD) + (b % MOD); ret %= MOD; return ret; } int sub(int a, int b) { int ret = (a % MOD) - (b % MOD); ret = (ret + MOD) % MOD; return ret; } int GCD(int a, int b) { if (b == 0) { return a; } return GCD(b, a % b); } struct pqComp { bool operator()(const pair<int, int>& p1, const pair<int, int>& p2) { return (p1.F < p2.F) || (p1.F == p2.F && p1.S < p2.S); } }; bool pCompF(pair<int, int>& p1, pair<int, int>& p2) { return p1.F < p2.F; } bool pCompS(const pair<int, int>& p1, const pair<int, int>& p2) { return p1.S < p2.S; } bool pCompFS(pair<int, int>& p1, pair<int, int>& p2) { return (p1.S < p2.S) || (p1.S == p2.S && p1.F < p2.F); } int n; struct segtree { pair<ll,bool> t[4*N]; void merge(int v) { t[v].F = t[v * 2].F + t[v * 2 + 1].F; } void mark(int v) { t[v].F = 0; t[v].S = 1; } void push(int v) { if (t[v].S) { mark(v * 2); mark(v * 2 + 1); t[v].S = 0; } } void upd(int pos, int val, int v, int tl, int tr) { if (tl == tr) { t[v].F += val; return; } push(v); int m = tl + tr >> 1; if (pos <= m) { upd(pos, val, v * 2, tl, m); } else { upd(pos, val, v * 2 + 1, m + 1, tr); } merge(v); } ll get(int l, int r, int v, int tl, int tr) { if (r < tl || tr < l) { return 0; } if (l <= tl && tr <= r) { return t[v].F; } push(v); int m = tl + tr >> 1; return get(l, r, v * 2, tl, m) + get(l, r, v * 2 + 1, m + 1, tr); } } tt; struct SegTree { array<int, 3> t[4*N]; void build(int v, int tl, int tr) { t[v] = {inf, -inf, 0}; if (tl == tr) { return; } int m = tl + tr >> 1; build(v * 2, tl, m); build(v * 2 + 1, m + 1, tr); } void merge(int v) { t[v][0] = min(t[v * 2][0], t[v * 2 + 1][0]); t[v][1] = max(t[v * 2][1], t[v * 2 + 1][1]); } void mark(int v, int val) { t[v] = {val, val, val}; } void push(int v) { if (t[v][2]) { mark(v * 2, t[v][2]); mark(v * 2 + 1, t[v][2]); t[v][2] = 0; } } void upd(int l, int r, int val, int v, int tl, int tr) { if (r < tl || tr < l) { return; } if (l <= tl && tr <= r) { mark(v, val); return; } push(v); int m = tl + tr >> 1; upd(l, r, val, v * 2, tl, m); upd(l, r, val, v * 2 + 1, m + 1, tr); merge(v); } ll get(int l, int r, int v, int tl, int tr, segtree &tt) { if (r < tl || tr < l) { return 0; } if (l <= tl && tr <= r && t[v][0] == t[v][1]) { tt.upd(t[v][0], tr - tl + 1, 1, 1, n); return tt.get(1, t[v][0] - 1, 1, 1, n) * (tr - tl + 1); } push(v); int m = tl + tr >> 1; return get(l, r, v * 2 + 1, m + 1, tr, tt) + get(l, r, v * 2, tl, m, tt); } int get(int pos, int v, int tl, int tr) { if (tl == tr) { return t[v][0]; } push(v); int m = tl + tr >> 1; if (pos <= m) { return get(pos, v * 2, tl, m); } return get(pos, v * 2 + 1, m + 1, tr); } } t; vector<int> g[N]; int timer = 0, pr[N], sz[N], h[N], tin[N]; void dfs(int v, int p = 0) { sz[v] = 1; if (p) { g[v].erase(find(all(g[v]), p)); } for (int &u: g[v]) { dfs(u, v); if (sz[u] > sz[g[v][0]]) { swap(u, g[v][0]); } sz[v] += sz[u]; } } void dfs1(int v) { tin[v] = ++timer; if (g[v].size()) { h[g[v][0]] = h[v]; } for (int u: g[v]) { pr[u] = v; dfs1(u); } } ll get(int v, int val) { ll ans = 0; while (h[v] > 1) { ans += t.get(tin[h[v]], tin[v], 1, 1, n, tt); t.upd(tin[h[v]], tin[v], val, 1, 1, n); v = pr[h[v]]; } ans += t.get(1, tin[v], 1, 1, n, tt); t.upd(1, tin[v], val, 1, 1, n); tt.mark(1); return ans; } void solve() { cin >> n; vector<int> a(n + 1); vector<int> b; for (int i = 1; i <= n; ++i) { cin >> a[i]; b.pub(a[i]); } sort(all(b)); b.erase(unique(all(b)), b.end()); for (int i = 1; i <= n; ++i) { a[i] = lower_bound(all(b), a[i]) - b.begin() + 1; } vector<pair<int,int>> e(n); for (int i = 1; i < n; ++i) { cin >> e[i].F >> e[i].S; g[e[i].F].pub(e[i].S); g[e[i].S].pub(e[i].F); } dfs(1); iota(h + 1, h + n + 1, 1); dfs1(1); t.build(1, 1, n); for (int i = 1; i <= n; ++i) { t.upd(tin[i], tin[i], a[i], 1, 1, n); } for (int i = 1; i < n; ++i) { cout << get(e[i].F, t.get(tin[e[i].S], 1, 1, n)) << '\n'; } } signed main() { speed; int T = 1; //cin >> T; while (T--) { solve(); } } /* НЕ ЗАХОДИТ РЕШЕНИЕ? 1) ПРОВЕРЬ НА ОЧЕВИДНЫЕ ОШИБКИ В КОДЕ 2) ПРОВЕРЬ НА ПЕРЕПОЛНЕНИЯ 3) УБЕДИСЬ В ПРАВИЛЬНОСТИ АЛГОРИТМА */

construction.cpp:27:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   27 | const int INF = 1e18;
      |                 ^~~~