1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
const int N=222222;
vector<int>e[N];
int n,ans,cnt,tot_seg;
int a[N],b[N],Rt[N];
int Ls[N*20],Rs[N*20],vai[N*20],vad[N*20];
int fi[N],fd[N];
int gi[N],gd[N];
void mer_ge(int &x,int y)
{
if(!x||!y) {x^=y;return;}
ckmax(vai[x],vai[y]),ckmax(vad[x],vad[y]);
ckmax(ans,max(vai[Ls[x]]+vad[Rs[y]],vad[Rs[x]]+vai[Ls[y]]));
mer_ge(Ls[x],Ls[y]),mer_ge(Rs[x],Rs[y]);
}
inline void push_up(int x,int opt){!opt?vai[x]=max(vai[Ls[x]],vai[Rs[x]]):vad[x]=max(vad[Ls[x]],vad[Rs[x]]);}
void modify(int pos,int l,int r,int &x,int k,int opt)
{
if(!x) x=++tot_seg;
if(l==r) {!opt?ckmax(vai[x],k):ckmax(vad[x],k);return;}
int mid=(l+r)>>1;
pos<=mid?modify(pos,l,mid,Ls[x],k,opt):modify(pos,mid+1,r,Rs[x],k,opt);
push_up(x,opt);
}
int query(int L,int R,int l,int r,int x,int opt)
{
if(!x) return 0;
if(L<=l&&r<=R) return !opt?vai[x]:vad[x];
int mid=(l+r)>>1,ret=-(1e9+7);
if(L<=mid) ckmax(ret,query(L,R,l,mid,Ls[x],opt));
if(mid<R) ckmax(ret,query(L,R,mid+1,r,Rs[x],opt));
return ret;
}
void dfs(int u,int f)
{
for(int v:e[u]) if(v^f)
{
dfs(v,u);
gi[u]=query(1,a[u]-1,1,cnt,Rt[v],0),gd[u]=query(a[u]+1,cnt,1,cnt,Rt[v],1);
ckmax(ans,max(gi[u]+fd[u]+1,gd[u]+fi[u]+1));
ckmax(fi[u],gi[u]),ckmax(fd[u],gd[u]);
mer_ge(Rt[u],Rt[v]);
}
modify(a[u],1,cnt,Rt[u],fi[u]+1,0),modify(a[u],1,cnt,Rt[u],fd[u]+1,1);
}
signed main()
{
n=read();if(n==1) return puts("1")&0;
R(i,1,n) b[i]=a[i]=read();
sort(b+1,b+n+1);cnt=unique(b+1,b+n+1)-b-1;
R(i,1,n) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
int u,v;R(i,2,n) u=read(),v=read(),e[u].pb(v),e[v].pb(u);
dfs(1,0);
writeln(ans);
}
|