语文题，要读懂题意...
题目中的双亲节点就是父节点的意思
部门的意思是有边直接相连的子图
求的是 最大的部门节点子集 ，意思是对于所有部门，在所有部门选出一些子集，使得子集并起来后的大小最大，并且并起来的子集中的节点满足对于任意祖先后代节点，祖先的节点值小于等于后代的节点值
题面好像没有保证父节点编号比儿子小......但是数据就是这个样子.......所以应该是默认 $1$ 号节点为根了...不然也没法做了......
对于每一个节点，开一个从小到大的集合 $S[x]$
设 $S[x]$ 的大小为 $T$，那么对于 $S[x]$ 从左到右，从小到大的第 $i$ 个数，它表示在 $x$ 的子树中最优选出 $T-i+1$ 个节点的集合中最小的节点值的最大值
或者为了方便理解把数从右到左看也行，从大到小的第 $i$ 个数就是它表示在 $x$ 的子树中最优选出 $i$ 个节点的集合中最小的节点值的最大值
为了方便代码，集合是从小到大的
显然，$T$ 就相当于节点 $x$ 的子树中的 最大部门节点子集 的集合大小，
理解这些后考虑用儿子的 $S[v]$ 维护 $S[x]$
考虑两个儿子合并的情况，因为儿子之间不存在祖先后代关系，所以可以直接贪心全部合并进来，合并后的 $S[x]$ 同样满足我们对 $S$ 的定义
儿子合并完后考虑本身的值 $val[x]$ 加入 $S[x]$ 中
因为 $x$ 是它子树中所有节点的祖先，又要保证 $S[x]$ 的定义正确
设 $t$ 为原本集合里第一个小于 $val[x]$ 的位置，为了维护 $S[x]$ 的定义显然我们要把 $S[x][t]$ 替换成 $val[x]$
（不然对于 $S[x][t]$ 对应的集合，我们显然可以把那个值为 $S[x][t]$ 的节点换成 $x$，使 $S[x][t]$ 更大）
这样首先 $S[x][t]$ 右边的值的定义显然受不会影响， 且$S[x][t]$ 就被修改成正确的定义
对于左边的值，显然我们加入 $x$ 最多只能替换集合的一个节点，且 $x$ 加入后所有小于 $val[x]$ 的节点都不能加入集合
所以如果我们要替换 $S[x][i] (i<t)$ 对应的集合中一个值为 $S[x][i]$ 的节点，我们必须还要先替换掉所有其他值为 $S[x][k] (kin [i+1,t])$ 的节点（比如之前的 $S[x][t]$），所以不能替换，所以左边的值不会改变
然后一波 $dfs$ 加启发式合并就好了
复杂度 $O(nlog^2_n)$，代码非常简单
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<set> #include<vector> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7; int n,val[N]; multiset <int> S[N]; multiset <int>::iterator it; vector <int> v[N]; inline void merge(int x,int y) { if(S[x].size()<S[y].size()) swap(S[x],S[y]); for(it=S[y].begin();it!=S[y].end();it++) S[x].insert(*it); } void dfs(int x) { for(int i=v[x].size()-1;i>=0;i--) dfs(v[x][i]),merge(x,v[x][i]); S[x].insert(val[x]); it=S[x].lower_bound(val[x]); if(it!=S[x].begin()) S[x].erase(--it); } int main() { n=read(); int a; for(int i=1;i<=n;i++) val[i]=read(); for(int i=2;i<=n;i++) a=read(),v[a].push_back(i); dfs(1); printf("%d",S[1].size()); return 0; }