#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
using namespace std;
const int blok=450;
int n;
int val[200023],loc[200023];
vector<int>komsu[200023];
int dep[200023],eu[200023],son[200023];
int tim=0;
int spar[400023][19],lg[400023];
int from[200023];
ll dp[200023];
int v[200023];
int bigger[200023];
int siz=0;
void dfs(int pos){
spar[++tim][0]=pos;
eu[pos]=tim;
for(int x:komsu[pos]){
if(eu[x])continue;
dep[x]=dep[pos]+1;
dfs(x);
spar[++tim][0]=pos;
}
son[pos]=tim;
}
int lca(int l,int r){
if(eu[l]>eu[r])swap(l,r);
l=eu[l];r=eu[r];
int a=spar[l][lg[r-l+1]],b=spar[r-(1<<lg[r-l+1])+1][lg[r-l+1]];
if(dep[a]<dep[b])return a;
return b;
}
int dis(int a,int b){
return dep[a]+dep[b]-2*dep[lca(a,b)];
}
void dfs2(int pos,int m){
for(int x:komsu[pos]){
if(dep[x]<dep[pos])continue;
bigger[x]=bigger[pos]+(val[pos]>=m);
dfs2(x,m);
}
}
void cal(){
int m=n+1;
{
int x=v[0];
while(x!=n+1){
m=min(val[x],m);
x=v[x];
}
}
siz=0;
v[0]=n+1;
queue<int>q;
for(int i=1;i<m;i++){
bigger[i]=0;
from[loc[i]]=0;
}
for(int i=m;i<=n;i++){
q.push(loc[i]);
while(q.size()){
int pos=q.front();
q.pop();
from[pos]=loc[i];
for(int x:komsu[pos]){
if(val[x]>=i||from[x])continue;
q.push(x);
}
}
}
dfs2(1,m);
}
void ekle(int x){
siz++;
for(int p=0;p!=n+1;p=v[p]){
if((p==0||eu[p]<eu[x])&&(v[p]==n+1||eu[v[p]]>eu[x])){
v[x]=v[p];
v[p]=x;
return;
}
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin>>n;
for(int i=2;i<=n*2;i++){
lg[i]=lg[i/2]+1;
}
for(int i=1;i<=n;i++){
cin>>val[i];
loc[val[i]]=i;
}
for(int i=1;i<n;i++){
int x,y;cin>>x>>y;
komsu[x].pb(y);
komsu[y].pb(x);
}
dfs(1);
for(int i=1;i<19;i++){
for(int j=1;j+(1<<i)-1<=tim;j++){
spar[j][i]=spar[j][i-1];
int x=spar[j+(1<<(i-1))][i-1];
if(dep[x]<dep[spar[j][i]])spar[j][i]=x;
}
}
v[0]=n+1;
ekle(loc[n]);
ll ans=0;
cal();
for(int i=n-1;i>=1;i--){
if(siz>=blok){
cal();
}
int par=0;
for(int p=v[0];p!=n+1;p=v[p]){
if(eu[loc[i]]>eu[p]&&eu[loc[i]]<=son[p]){
par=p;
}
}
if(par!=0&&bigger[loc[i]]==bigger[par]){
from[loc[i]]=par;
}
int las=0;
for(int p=v[par];p!=n+1;p=v[p]){
if(p==par){
las=0;
continue;
}
if(par!=0&&eu[p]>son[par])break;
if(las&&eu[p]<=son[las])continue;
las=p;
if(bigger[loc[i]]+bigger[p]==2*bigger[lca(loc[i],p)]){
if(val[p]<val[from[loc[i]]])from[loc[i]]=p;
}
}
ekle(loc[i]);
dp[loc[i]]=dp[from[loc[i]]]+dis(loc[i],from[loc[i]]);
ans=max(ans,dp[loc[i]]);
}
cout<<ans;
}
# | 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... |