选点(dfs序+lis)

思路：
这个题意我读了半年
样例的3是这样的

这里为什么不选4号节点呢，因为“如果在左子树选了一个点，在右子树中选的其他点要比它小。”，也就是左子树的值应该比右子树的值大，并且根节点的值最小，那么我们可以知道 根节点<右子树<左子树，那么我们可以根-右-左这样遍历这棵树，然后存他的dfs序，要使得选择的节点数量越多，就是在这个dfs序找一个最长上升子序列，这个长度就是答案。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
int G[maxn][2];
int w[maxn];
int dfn[maxn],tot = 0;
int st[maxn],top = 0;
void dfs(int u){
    if(u == 0)return ;
    dfn[++tot] = u;
    dfs(G[u][1]);
    dfs(G[u][0]);
}
void solved(){
    int n;scanf("%d",&n);
    for(int i = 1; i <= n; i++)scanf("%d",&w[i]);
    for(int i = 1; i <= n; i++){
        int u,v;scanf("%d%d",&u,&v);
        G[i][0] = u;
        G[i][1] = v;
    } 
    dfs(1);
    int ans = 1;
    st[++top] = w[dfn[1]];
    for(int i = 2; i <= tot; i++){
        if(w[dfn[i]] > st[top])st[++top] = w[dfn[i]];
        else{
            int index = upper_bound(st + 1,st + 1 + top,w[dfn[i]]) - st;
            st[index] = w[dfn[i]];
        }
    }
    printf("%d\n",top);
}
int main(){
    solved();
    return 0;
}