#include <bits/stdc++.h> /* Checklist: - Check statement: - Check filename: - Check test limit: - Stresstest: */ using namespace std; using ll = long long; #define int long long #define pii pair<ll, ll> #define fi first #define se second const ll N = 5e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 19; int n, a[N]; vector <int> adj[N]; int h[N], dist[N]; pii st[N][lim + 1]; int in[N], tdfs; int lg[N]; void dfs(int u, int par) { in[u] = ++tdfs; st[tdfs][0] = make_pair(h[u], u); for (auto v : adj[u]) { if (v != par) { h[v] = h[u] + 1; dfs(v, u); st[++tdfs][0] = make_pair(h[u], u); } } } void build() { dfs(1, 0); for (int i = 2; i <= tdfs; i++) lg[i] = lg[i / 2] + 1; for (int i = 1; i <= lim; i++) { for (int j = 1; j + (1 << i) - 1 <= tdfs; j++) { st[j][i] = min(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]); } } } int get(int x, int y) { int l = in[x], r = in[y]; if (l > r) swap(l, r); int k = lg[r - l + 1]; return min(st[l][k], st[r - (1 << k) + 1][k]).se; } int getdist(int u, int v) { int anc = get(u, v); return h[u] + h[v] - 2 * h[anc]; } vector <int> pre; bool cmp(int x, int y) { return a[x] < a[y]; } int dp[N]; int p[N]; int find(int u) { // dp[p[u]] = max(dp[u], dp[p[u]]); if (p[u] == u) return u; return p[u] = find(p[u]); } signed main() { ios::sync_with_stdio(false); cin.tie(0); if (fopen(".inp", "r")) { freopen(".inp", "r", stdin); freopen(".out", "w", stdout); } cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } build(); for (int i = 1; i <= n; i++) p[i] = i; for (int i = 1; i <= n; i++) pre.push_back(i); sort(pre.begin(), pre.end(), cmp); // for (auto x : pre) cout << x << ' '; // cout << '\n'; // cout << '\n'; // cout << get(3, 4) << '\n'; for (auto u : pre) { for (auto v : adj[u]) { if (a[v] < a[u]) { int t = find(v); // cout << u << ' ' << v << ' ' << t << ' ' << dp[t] << ' ' << getdist(u, t) << '\n'; dp[u] = max(dp[u], dp[t] + getdist(u, t)); p[t] = u; } } } // for (int i = 1; i <= n; i++) cout << dp[pre[i - 1]] << ' '; cout << dp[pre.back()]; return 0; }

Main.cpp: In function 'int main()':
Main.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~