#include <bits/stdc++.h> #define L(i, j, k) for(int i = (j); i <= (k); i++) #define R(i, j, k) for(int i = (j); i >= (k); i--) #define ll long long #define sz(a) ((int) a.size()) #define all(a) a.begin(), a.end() #define vi vector<int> #define pb emplace_back #define me(a, x) memset(a, x, sizeof(a)) #define fst first #define snd second #define ii pair<int, int> using namespace std; const int MAXN=2e5+5,LOG=20,INF=1e9; int lnk[MAXN],tam[MAXN],bst[MAXN],ans[MAXN],dist[MAXN],dist2[MAXN],up[MAXN][LOG],n; int val[MAXN]; vi adj[MAXN],adjr[MAXN]; bool lib[MAXN]; int jump(int a,int k){ L(i,0,LOG-1){ if((1<<i)&k)a=up[a][i]; } return a; } int lca(int a,int b){ if(dist[a]>dist[b])swap(a,b); b=jump(b,dist[b]-dist[a]); if(a==b)return a; R(i,LOG-1,0){ if(up[a][i]!=up[b][i]){ a=up[a][i]; b=up[b][i]; } } return up[a][0]; } void dfs(int u,int par,int d=0){ dist[u]=d; for(auto v:adj[u]){ if(v==par)continue; up[v][0]=u; dfs(v,u,d+1); } } int find(int a){ while(lnk[a]!=a)a=lnk[a]; return a; } void dsu(int a,int b){ a=find(a),b=find(b); assert(a!=b); if(tam[a]<tam[b])swap(a,b); lnk[b]=a; tam[a]+=tam[b]; if(val[bst[a]]<val[bst[b]])bst[a]=bst[b]; adjr[bst[a]].pb(bst[b]); adjr[bst[b]].pb(bst[a]); } int getDistance(int a,int b){ return dist[a]+dist[b]-dist[lca(a,b)]*2; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin>>n; vector<ii>p; L(i,1,n){ tam[i]=1; ans[i]=0; cin>>val[i]; p.pb(val[i],i); bst[i]=i; lnk[i]=i; } L(i,0,n-2){ int a,b;cin>>a>>b; adj[a].pb(b); adj[b].pb(a); } dfs(1,-1); //~ cout<<"PASS"<<endl; L(i,1,LOG-1){ L(j,1,n){ up[j][i]=up[up[j][i-1]][i-1]; } } sort(all(p)); L(i,0,n-1){ lib[p[i].snd]=1; for(int v:adj[p[i].snd]){ if(!lib[v])continue; //~ cout<<p[i].snd<<" "<<v<<endl; dsu(p[i].snd,v); } } //~ cout<<"PASS2"<<endl; queue<int>q; q.push(p[n-1].snd); //~ cout<<p[n].snd<<endl; L(i,1,n)dist2[i]=-INF; dist2[p[n-1].snd]=0; while(sz(q)){ int u=q.front();q.pop(); //~ cout<<u<<endl; for(int v:adjr[u]){ //~ cout<<v<<endl; if(dist2[v]!=-INF)continue; dist2[v]=dist2[u]+getDistance(u,v); q.push(v); } } cout<<*max_element(dist2+1,dist2+n+1)<<endl; }