我们尝试类比序列上的情况来看这一题。
对于序列上的情况，我们维护一个集合 \(S\) ，其中 \(S_i\) 表示，长度为 \(i\) 的最长不下降子序列的最后一项的最小值。 那么，对于新的点，我们考虑两种情况：它能加长序列，那么就加长；否则，就尽可能地更新最小值。
对于树上的情况，我们首先尝试考虑一种 \(O(n^2logn)\) 的做法。我们对于每一个节点维护一个集合 \(S_i\)， 其中 \(S_{i,j}\) 表示仅用到这个节点及其子树内的所有点，能够构造的大小为 \(j\) 的集合的最小项的最大值。
如果我们把所有子节点的 \(S\) 都已经整合在一起了，那么更新根节点是比较容易的：类比于序列即可。 问题在于子节点要如何合并。
仔细观察，发现，子节点的合并是一个类似于归并的操作。 这样我们就有了一个 \(O(n^2logn)\) 的「高」效做法。
怎么优化这个做法呢？ 我们不妨考虑重链剖分启发式合并。这样就将复杂度优化到了 \(O(nlog^2n)\) ，足以通过此题。 具体来说，我们对于每个节点开一个map，然后暴力合并。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int N=200005;
struct ee{
int v;
int nxt;
}e[N];
int h[N],et=0;
inline void add(int U,int V){
e[++et]=(ee){V,h[U]};
h[U]=et;
}
int w[N],sz[N],sn[N],dep[N],fa[N];
int id[N];
multiset<int> lst[N];
int n;
inline void dfs0(int X){
sn[X]=0,sz[X]=1;
for(int i=h[X];i;i=e[i].nxt){
dfs0(e[i].v);
sz[X]+=sz[e[i].v];
if(sz[sn[X]]<sz[e[i].v]){
sn[X]=e[i].v;
}
}
}
inline void dfs1(int X){
if(sn[X]){
dfs1(sn[X]);
id[X]=id[sn[X]];
}
for(int i=h[X];i;i=e[i].nxt){
if(e[i].v==sn[X]){
continue;
}
dfs1(e[i].v);
lst[id[X]].insert(lst[id[e[i].v]].begin(),lst[id[e[i].v]].end());
}
lst[id[X]].insert(w[X]);
multiset<int>::iterator it=lst[id[X]].lower_bound(w[X]);
if(it!=lst[id[X]].begin()){
--it;lst[id[X]].erase(it);
}
}
void init(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&w[i]);
id[i]=i;
}
int x;
for(int i=2;i<=n;++i){
scanf("%d",&x);
fa[i]=x;add(x,i);
}
dfs0(1);
dfs1(1);
printf("%d\n",lst[id[1]].size());
}
int main(){
init();
return 0;
}