#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int p[N],pa[N],dp[N][20],d[N],dpb[N];
vector<int> adj[N];
bool cp(int a,int b){
return p[a]<p[b];
}
void dfs(int u,int p){
for(auto v:adj[u]){
if(v==p) continue;
dp[v][0]=u;
d[v]=d[u]+1;
dfs(v,u);
}
}
int lca(int a,int b){
//make same depth (put b up)
if(d[b]<d[a]) swap(a,b);
for(int i=19;i>=0;i--) if(d[dp[b][i]]>=d[a]) b=dp[b][i];
if(a==b) return a;
for(int i=19;i>=0;i--) if(dp[b][i]!=dp[a][i]) a=dp[a][i],b=dp[b][i];
return dp[a][0];
}
int path(int a,int b){
return d[a]+d[b]-2*d[lca(a,b)];
}
int root(int x){
if(pa[x]==x) return x;
return pa[x]=root(pa[x]);
}
void merge(int a,int b){
int ra=root(a),rb=root(b);
if(ra==rb) return;
//root is the node that has maximum height
if(p[ra]>p[rb]) pa[rb]=ra;
else pa[ra]=rb;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>p[i];
for(int i=1;i<=n;i++) pa[i]=i;
for(int i=0;i<n-1;i++){
int u,v;
cin>>u >>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> sp;
for(int i=1;i<=n;i++) sp.push_back(i);
sort(sp.begin(),sp.end(),cp);
dfs(sp.back(),-1);
dp[sp.back()][0]=sp.back();
for(int i=1;i<20;i++) for(int j=1;j<=n;j++) dp[j][i]=dp[dp[j][i-1]][i-1];
for(auto u:sp){
for(auto v:adj[u]){
if(p[v]>p[u]) continue;
//cout<<u <<" " <<v <<" " <<dpb[u] <<" " <<dpb[v]+path(u,root(v)) <<"\n";
//cout<<root(u) <<" " <<root(v) <<"\n";
dpb[u]=max(dpb[u],dpb[root(v)]+path(u,root(v)));
merge(u,v);
//cout<<root(u) <<" " <<root(v) <<"\n";
}
}
cout<<dpb[sp.back()];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |