题意

• n个结点的二叉树，1为根，每个结点有一个权值
• 要选择尽可能多的点，选点要满足如下要求
  1. 选了根那子树中的所有选择的点要比根更大
  2. 左子树选了一个点，右子树选的点要比他小

思路

• 对于选择规则，其实就是满足左结点>右结点>根
• 不妨维护根右左的dfn序，这样子找的就是dfn序中最长上升子序列
• LIS的朴素维护 ，用二分优化使得复杂度变为
• 二分优化方法
  • 维护一个数组d[i]记录长为i的LIS的最小结尾
  • 每新添一个元素，lower_bound找第一个大于等于它的
    • 如果存在就替换掉它，扩充后面的空间
    • 如果不存在说明，当前元素会构成新的LIS给dpush_back当前元素
  • 最后d[i]的size就是LIS的长度
  • lower_bound找大于等的被替换，这样保证序列是严格单增的
  • upper_bound找大于的被替换，这样保证序列是不下降的的

代码

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

int v[202020];
struct ty{
    int l,r;
}t[202020];

int tim;
int b[202020];
vector<int>d;
void dfs(int x){
    b[++tim]=v[x];
    if(t[x].r) dfs(t[x].r);
    if(t[x].l) dfs(t[x].l);
}

int main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> v[i];
    }
    for(int i=1;i<=n;i++){
        cin >> t[i].l >> t[i].r;
    }
    dfs(1);
    for(int i=1;i<=n;i++){
        auto p=lower_bound(d.begin(),d.end(),b[i]);
        if(p==d.end()) d.push_back(b[i]);
        else *p=b[i];
    }
    cout << d.size() << endl;
    return 0;
}