选点

思路：
把树上的点的权值按的顺序排列，题目意思就变成就求这个序列的最长递增子序列。

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+7,maxm=2e5+7;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int to[maxm][2],val[maxm];
int que[maxn],top,d[maxn],tot;
void dfs(int x) {
    if(!x) return;
    que[++top]=val[x];
    dfs(to[x][1]);
    dfs(to[x][0]);
}
int main() {
    int n=read();
    for(int i=1;i<=n;++i) val[i]=read(); 
    for(int i=1,u,v;i<=n;++i) {
        u=read(),v=read();
        to[i][0]=u,to[i][1]=v;
    }
    dfs(1);
    d[++tot]=que[1];
    for(int i=2,pos;i<=top;++i) {
        if(que[i]>d[tot]) d[++tot]=que[i];
        else {
            pos=lower_bound(d+1,d+1+tot,que[i])-d;
            d[pos]=que[i];
        }
    }
    printf("%d\n",tot);
    return 0;
}