选点

做法：dfs序+LIS

思路：

• 因为这是棵二叉树，所以可以使用结构体存储
• 由如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大可以得出根节点<左节点，根节点<右节点
  由如果在左子树选了一个点，在右子树中选的其他点要比它小可以得出右节点<左节点
  所以根节点<右节点<左节点 根据递增关系可以进行根节点->右节点->左节点的访问顺序遍历
• 选出尽量多的点可以转化为遍历二叉树的顺序求最长上升子序列（LIS）的长度，这里采用贪心的思想 不会的可以参考 最长不下降子序列 稍作修改即可

代码

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
const double eps=1e-6;
const double PI=acos(-1.0);

int n,dp[N];
struct node{
    int l,r;
    ll w;
}tree[N];

vector<ll> dfn;

void dfs(int u){
    if(!u) return;
    dfn.pb(tree[u].w);
    dfs(tree[u].r);
    dfs(tree[u].l);
}

void solve(){
    cin>>n;
    rep(i,1,n) cin>>tree[i].w;
    rep(i,1,n){
        cin>>tree[i].l>>tree[i].r;
    }
    dfs(1);
    fill(dp,dp+n,INF);
//    for(auto x:dfn){
//        cout<<x<<" ";
//    }
    int m=dfn.size();
    for(int i=0;i<m;i++){
        *lower_bound(dp,dp+m,dfn[i])=dfn[i];
    }
    cout<<lower_bound(dp,dp+m,INF)-dp<<"\n";
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef DEBUG
    freopen("F:/laji/1.in", "r", stdin);
//    freopen("F:/laji/2.out", "w", stdout);
#endif
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}