题目链接：选点

看似像树形dp，而且还很麻烦。

但是我们可以注意一下，这是二叉树，大小关系为： 左儿子 > 右儿子 > 根

所以如果我们先遍历根，然后往右儿子走，然后往左儿子走，的dfs序。

然后就是求LIS就行了。

比较思维。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,w[N],ls[N],rs[N],d[N],a[N],cnt;
void dfs(int x){
    if(!x)  return ;
    a[++cnt]=w[x];
    dfs(rs[x]);    dfs(ls[x]);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)   scanf("%d",&w[i]);
    for(int i=1;i<=n;i++)   scanf("%d %d",&ls[i],&rs[i]);
    dfs(1); cnt=1;  d[1]=a[1];
    for(int i=2;i<=n;i++){
        if(a[i]>d[cnt]) d[++cnt]=a[i];
        else    d[lower_bound(d+1,d+1+cnt,a[i])-d]=a[i];
    }
    cout<<cnt<<endl;
    return 0;
}