选点_牛客博客

题意

你有一棵 $n$ 个节点的二叉树，每个节点有权值 $w_i$ ，你要选尽量多的点，但是得满足以下限制：
对于任意一棵子树，都要满足：
如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大；
如果在左子树选了一个点，在右子树中选的其他点要比它小。

分析

根的值 $<$ 右子树的最大值 $<$ 左子树的最大值，如果要选择最多的点，那么如果能够处理出根 $\color\pink到$ 右子树 $\color\pink到$ 左子树的 $dfs$ 序，在序列上维护一个最长上升子序列，就能选到最多的点。答案就是序列长度。

代码

#include<bits/stdc++.h>
#define int long long
const int N=1e6+5,INF=0x3f3f3f3f,mod=998244353;
using namespace std;

int n,tot,cnt;
int w[N],l[N],r[N],a[N],ans[N];

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

int qpow(int a,int b)
{
    int ans=1;
    while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}
    return ans;
}

void dfs(int x)
{
    if(x==0)    return ;
    a[++tot]=w[x];
    dfs(r[x]);dfs(l[x]);
}

signed main()
{
    n=read();
    for(int i=1;i<=n;i++) w[i]=read();
    for(int i=1;i<=n;i++) l[i]=read(),r[i]=read();
    dfs(1);
    ans[++cnt]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(a[i]>ans[cnt])    ans[++cnt]=a[i];
        else
        {
            int py=upper_bound(ans+1,ans+1+cnt,a[i])-ans;
            ans[py]=a[i];
        }
    }
    printf("%lld",cnt);
    return 0;
}
/*
5
1 5 4 2 3
3 2
4 5
0 0
0 0
0 0 
*/