我们对整棵树进行dfs遍历，并用一个multiset维护对于每个点，它的子树可取的最大点集。
我们遍历到点$u$时：
不选点$u$，显然答案就为它的所有子树的子集大小之和（所以答案是单调不减的）
选点$u$时，我们lower_bound一个比$val[u]$小且最接近$val[u]$的权值，用$val[u]$替换它。
为什么可以酱紫做呢
试想一下，当multiset中的元素都被替换到比点$k$的权值$val[k]$大时
这时把$val[k]$扔进去，就相当于找到了一种更优的子集取法。
虽然替换后multiset表示的子集不一定合法
但是答案单调不减（为multiset的大小）啊
所以没什么关系辣
#include<iostream> #include<cstdio> #include<cstring> #include<set> #define rint register int using namespace std; void read(int &x){ char c=getchar();x=0; while(c<‘0‘||c>‘9‘) c=getchar(); while(‘0‘<=c&&c<=‘9‘) x=x*10+(c^48),c=getchar(); } #define N 200005 int n,v[N]; int cnt,hd[N],nxt[N],ed[N],poi[N]; multiset<int> h[N]; multiset<int>::iterator it; inline void adde(int x,int y){ nxt[ed[x]]=++cnt, hd[x]=hd[x]?hd[x]:cnt, ed[x]=cnt, poi[cnt]=y; } void merge(int x,int y){ if(h[x].size()<h[y].size()) swap(h[x],h[y]); for(it=h[y].begin();it!=h[y].end();++it) h[x].insert(*it); } void dfs(int x){ for(int i=hd[x];i;i=nxt[i]) dfs(poi[i]),merge(x,poi[i]); h[x].insert(v[x]); it=h[x].lower_bound(v[x]); if(it!=h[x].begin()) h[x].erase(--it); } int main(){ read(n); for(rint i=1;i<=n;++i) read(v[i]); for(rint i=2,f;i<=n;++i) read(f),adde(f,i); dfs(1); printf("%d",h[1].size()); return 0; }
原文：https://www.cnblogs.com/kafuuchino/p/10688729.html