#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 2*1e5+5, INF = 4e18+9; struct DSU{ int n; vector<int> pa, sz; DSU(int n) : n(n){ pa.resize(n+1); sz.resize(n+1, 1); for(int i = 0; i <= n; i++){ pa[i] = i; } }; int find(int x){ while(x != pa[x]){ x = pa[x] = pa[pa[x]]; } return x; } bool same(int x, int y){ return find(x) == find(y); } bool merge(int x, int y){ x = find(x); y = find(y); if(x == y) return false; pa[y] = x; sz[x] += sz[y]; return true; } int size(int x){ return sz[find(x)]; } }; struct Tree{ int n, root; vector<int> depth, head, sz, pa; vector<int> f; Tree(int n, int root, vector<vector<int>> &adj): n(n), root(root){ depth.resize(n+1, -1); head.resize(n+1); sz.resize(n+1, 0); pa.resize(n+1, -1); auto rootTree = [&](auto rootTree, int u, int p) -> void{ depth[u] = depth[p]+1; pa[u] = p; sz[u] = 1; for(int v : adj[u]){ if(v == p) continue; rootTree(rootTree, v, u); sz[u] += sz[v]; } }; rootTree(rootTree, root, 0); auto decompose = [&](auto decompose, int u, int h) -> void{ head[u] = h; int heavy = -1; for(int v : adj[u]){ if(v == pa[u]) continue; if(heavy == -1 || sz[heavy] < sz[v]) heavy = v; } if(heavy != -1) decompose(decompose, heavy, h); for(int v : adj[u]){ if(v == pa[u] || v == heavy) continue; decompose(decompose, v, v); } }; decompose(decompose, root, root); f = [&]{ vector<array<int, 2>> first(n+1); vector<array<int, 2>> second(n+1); function<void(int, int)> dfs0 = [&](int u, int p) { first[u] = second[u] = {0, -1}; for (int v : adj[u]) { if (v == p) { continue; } dfs0(v, u); auto fetch = first[v]; fetch[0] += 1; fetch[1] = v; if (fetch > first[u]) { swap(fetch, first[u]); } if (fetch > second[u]) { swap(fetch, second[u]); } } }; dfs0(1, 0); function<void(int, int)> dfs = [&](int u, int p) { for (int v : adj[u]) { if (v == p) { continue; } auto fetch = first[u][1] == v ? second[u] : first[u]; fetch[0] += 1; fetch[1] = u; if (fetch > first[v]) { swap(fetch, first[v]); } if (fetch > second[v]) { swap(fetch, second[v]); } dfs(v, u); } }; dfs(1, 0); vector<int> f(n+1); for (int u = 1; u <= n; u++) { f[u] = first[u][0]; } return f; }(); }; int lca(int u, int v){ for(; head[u] != head[v]; v = pa[head[v]]){ if(depth[head[u]] > depth[head[v]]) swap(u, v); } if(depth[u] > depth[v]) swap(u, v); return u; } int dist(int u, int v) { return depth[u]+depth[v]-2*depth[lca(u, v)]; } }; void solve(){ int n; cin >> n; vector<int> a(n+1); for(int i = 1; i <= n; i++){ cin >> a[i]; } vector<vector<int>> adj(n+1); for(int i = 1; i < n; i++){ int u, v; cin >> u >> v; u = a[u]; v = a[v]; adj[u].push_back(v); adj[v].push_back(u); } DSU dsu(n+1); vector<vector<int>> tree(n+1); for(int i = 1; i <= n; i++){ for(int j : adj[i]){ if(j > i) continue; tree[i].push_back(dsu.find(j)); dsu.merge(i, dsu.find(j)); } } Tree Y(n, 1, adj); vector<ll> f(n+1); auto dfs = [&](auto dfs, int u) -> void{ f[u] = 0; for(int v : tree[u]){ dfs(dfs, v); f[u] = max(f[u], f[v] + Y.dist(u, v)); } }; dfs(dfs, n); cout << f[n]; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); }