思路
放眼整个题解区没有我这种解法，因此来写一篇题解。
既然要求我们选择一个节点作为根，那么我们就枚举根。
接下来的问题就是如何 \(\mathcal{O}(1)\) 或 \(\mathcal O(\log n)\) 计算贡献。
我们可以把节点分为四类：这个节点，这个节点的父亲，这个节点的儿子，另外的节点。
其中第 \(1/2\) 类非常容易解决。难解决的就是这个节点的儿子和另外的节点。
不妨考虑线段树，把这个节点所有的儿子压到一个区间内，为此，我们需要寻找一种新的编号方式。
原本正常把树拍扁都是根据 \(\mathcal DFS\) 序遍历的，现在我们需要以 \(\mathcal BFS\) 序遍历，而且以点 \(i\) 为根时，它原本的父亲 \(fa_i\) 也会变成它的儿子。
于是如此模拟即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int const N=1e6+10;
int n,go[N];
struct node{int w,id;}a[N];
int vis[N],fa[N],minx[N],maxx[N],c[N];
vector<int>b[N];
struct Segment_Tree{
#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)
int c[N<<2];
inline void build(int x,int l,int r){
if (l==r){c[x]=a[l].w;return;}
build(ls,l,mid);build(rs,mid+1,r);
c[x]=max(c[ls],c[rs]);
}
inline void update(int x,int l,int r,int p,int v){
if (l==r){c[x]=v;return;}
if (p<=mid) update(ls,l,mid,p,v);
else update(rs,mid+1,r,p,v);
c[x]=max(c[ls],c[rs]);
}
inline int query(int x,int l,int r,int ll,int rr){
if (ll<=l && r<=rr) return c[x];
int res=-2e9;
if (ll<=mid) res=max(res,query(ls,l,mid,ll,rr));
if (mid<rr) res=max(res,query(rs,mid+1,r,ll,rr));
return res;
}
}T;
inline bool cmp(node x,node y){return x.id<y.id;}
inline int solve(int x){
int la=0;
if (fa[x]) la=c[fa[x]],T.update(1,1,n,go[fa[x]],-2e9);
T.update(1,1,n,go[x],-2e9);
int res=c[x];
if (minx[x]<=maxx[x]) res=max(res,T.query(1,1,n,minx[x],maxx[x])+1);
if (minx[x]-1>=1) res=max(res,T.query(1,1,n,1,minx[x]-1)+2);
if (maxx[x]+1<=n) res=max(res,T.query(1,1,n,maxx[x]+1,n)+2);
if (fa[x]) res=max(res,la+1),T.update(1,1,n,go[fa[x]],la);
T.update(1,1,n,go[x],c[x]);
return res;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for (int i=1;i<=n;++i) cin>>a[i].w,c[i]=a[i].w;
queue<int>q;
for (int i=1;i<n;++i){
int u,v;cin>>u>>v;
b[u].push_back(v);
b[v].push_back(u);
}
q.push(1);vis[1]=1;a[1].id=1;
int cnt=1;
while (!q.empty()){
int x=q.front();q.pop();
minx[x]=cnt+1;vis[x]=1;
for (auto v:b[x]){
if (vis[v]) continue;
fa[v]=x;
a[v].id=++cnt;q.push(v);
}
maxx[x]=cnt;
}
for (int i=1;i<=n;++i) go[i]=a[i].id;
sort(a+1,a+n+1,cmp);
T.build(1,1,n);
int ans=9e18;
for (int i=1;i<=n;++i) ans=min(ans,solve(i));
cout<<ans<<'\n';
return 0;
}