选点

传送门

注意一下这两句话

如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大；

如果在左子树选了一个点，在右子树中选的其他点要比它小。

根节点比子节点都要小

右子树比左子树都要大

所以可以跑序维护最长上升子序列来写

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int n,l[maxn],r[maxn],a[maxn],id,top,w[maxn],ans[maxn];
void dfs(int u)
{
    if( u==0 )    return;
    a[++id] = w[u];
    dfs( l[u] ); dfs(r[u] );
}
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)    cin >> w[i];
    for(int i=1;i<=n;i++)
        cin >> l[i] >> r[i];
    dfs(1);
    ans[++top] = a[1];
    for(int i=2;i<=n;i++)
    {
        if( a[i]>ans[top] )    ans[++top] = a[i];
        else
        {
            int index = upper_bound( ans+1,ans+1+top,a[i] )-ans;
            ans[index] = a[i];
        }
    }
    cout << top;
}