#include <algorithm> #include <iostream> #include <vector> using namespace std; const int N = 200000; int aa[N], ii[N], dd[N], pp[N], qq[N], ds[N], rr[N], xx[N]; vector<int> ej[N]; int dfs0(int p, int i, int d) { dd[i] = d++, pp[i] = p; int s = 1, j_ = -1, k_ = 0; for (int j : ej[i]) if (j != p) { int k = dfs0(i, j, d); s += k; if (k_ < k) j_ = j, k_ = k; } qq[i] = j_; return s; } void dfs1(int p, int i, int q) { int j_ = qq[i]; qq[i] = q; for (int j : ej[i]) if (j != p) dfs1(i, j, j == j_ ? q : j); } int lca(int i, int j) { while (qq[i] != qq[j]) if (dd[qq[i]] > dd[qq[j]]) i = pp[qq[i]]; else j = pp[qq[j]]; return dd[i] < dd[j] ? i : j; } int dist(int i, int j) { return dd[i] + dd[j] - dd[lca(i, j)] * 2; } int find(int i) { return ds[i] < 0 ? i : (ds[i] = find(ds[i])); } void join(int i, int j) { i = find(i); j = find(j); if (i == j) return; if (ds[i] == ds[j]) ds[i]--; if (ds[i] < ds[j]) swap(i, j); ds[i] = j; if (aa[rr[j]] < aa[rr[i]]) rr[j] = rr[i]; } int main() { ios_base::sync_with_stdio(false), cin.tie(NULL); int n; cin >> n; for (int i = 0; i < n; i++) cin >> aa[i], ii[--aa[i]] = i; for (int h = 0; h < n - 1; h++) { int i, j; cin >> i >> j, i--, j--; ej[i].push_back(j); ej[j].push_back(i); } dfs0(-1, 0, 0); dfs1(-1, 0, 0); for (int i = 0; i < n; i++) ds[i] = -1, rr[i] = i; for (int a = 0; a < n; a++) { int i = ii[a], x = 0; for (int j : ej[i]) if (aa[j] < a) { int r = rr[find(j)]; x = max(x, xx[r] + dist(i, r)); join(i, j); } xx[i] = x; } cout << xx[ii[n - 1]] << '\n'; return 0; }