选点

题意：
有一棵n个节点的二叉树，1为根节点，每个节点有一个值wi。现在要选出尽量多的点。
对于任意一棵子树，都要满足：
如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大；
如果在左子树选了一个点，在右子树中选的其他点要比它小。

题解：
要满足
根节点的值最小，左子树的值大于右子树的值。
这样的话我们可以先按照根->右->左的顺序来求出一个dfs序
然后求一下LIS即可。

/*Keep on going Never give up*/
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long

#define endl '\n'
#define Accepted 0
#define AK main()
#define I_can signed
using namespace std;
const int maxn =2e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;

int cnt,tot;
int v[maxn];
int ls[maxn],rs[maxn];
int ans[maxn];
int ok[maxn];
void dfs(int x){
    if(!x) return ;
    ans[++tot]=v[x];
    dfs(rs[x]);
    dfs(ls[x]);
}

signed main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        ls[i]=x;
        rs[i]=y;
    }
    dfs(1);
    //for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
    ok[++cnt]=ans[1];
    for(int i=2;i<=n;i++){
        if(ans[i]>ok[cnt]) ok[++cnt]=ans[i];
        else{
            int pos=upper_bound(ok+1,ok+1+cnt,ans[i])-ok;
            ok[pos]=ans[i];
        }
    }
    cout<<cnt<<endl;
    return 0;

}