题干：
有一棵n个节点的二叉树，1为根节点，每个节点有一个值wi。现在要选出尽量多的点。
对于任意一棵子树，都要满足：
如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大；
如果在左子树选了一个点，在右子树中选的其他点要比它小。
输入描述:
第一行一个整数n。
第二行n个整数wi，表示每个点的权值。
接下来n行，每行两个整数a,b。第i+2行表示第i个节点的左右儿子节点。没有为0。
n,a,b≤105,−2×109≤wi≤2×109n,a,b≤105,−2×109≤wi≤2×109
输出描述:
一行一个整数表示答案。
示例1
输入
复制
51 5 4 2 33 24 50 00 00 0
输出
复制
3
解题报告：
注意依据题意，需要先遍历右子树，再遍历左子树。或者存权值直接存负值，然后先遍历左子树再遍历右子树(即正常dfs序)也可以。
AC代码：
#include<cstdio>#include<iostream>#include<algorithm>#include<queue>#include<ctime>#include<map>#include<vector>#include<set>#include<string>#include<cmath>#include<cstring>#define ll long long#define pb push_back#define pm make_pair#define fi first#define se secondusing namespace std;const int MAX = 2e5 + 5;int dfn[MAX],in[MAX],out[MAX];int id,n;int a[MAX],b[MAX];int ans[MAX];int w[MAX];void dfs(int cur,int root) {dfn[++id] = cur;in[cur] = id;if(b[cur] != 0)dfs(b[cur],cur);if(a[cur] != 0)dfs(a[cur],cur);out[cur] = id;}int DP() {int len = 0;for(int i = 1; i<=id; i++) dfn[i] = w[dfn[i]];ans[++len] = dfn[1];for(int i = 2; i<=id; i++) {if(dfn[i] > ans[len]) ans[++len] = dfn[i];else {int pos = lower_bound(ans+1,ans+len+1,dfn[i]) - ans;ans[pos] = dfn[i];}}return len;}int main() {cin>>n;for(int i = 1; i<=n; i++) scanf("%d",w+i);for(int i = 1; i<=n; i++) scanf("%d%d",a+i,b+i);dfs(1,0);printf("%d\n",DP());return 0 ;}
AC代码2：
#include<bits/stdc++.h>using namespace std;const int maxn = 1e5 + 10;int p[maxn], q[maxn], t[maxn];int lson[maxn], rson[maxn], cnt, len;void dfs(int rt) {if (!rt)return;dfs(lson[rt]);dfs(rson[rt]);q[++cnt] = p[rt]*(-1);}int main() {int n;cin >> n;for (int i = 1; i <= n; i++)cin >> p[i];for (int i = 1; i <= n; i++) {int x, y;cin >> x >> y;lson[i] = x, rson[i] = y;}dfs(1);t[1] = q[1];for (int i = 2; i <= n; i++) {int cur = lower_bound(t + 1, t + 1 + len,q[i]) - t;t[cur] = q[i];len = max(len, cur);}cout << len << endl;}
还有一种解法（Orz大佬）
这个dfs序(因为是后序遍历)完了之后是对离散化后的权值求最长下降子序列（也就是值是1~n，求最长下降子序列），
#include<bits/stdc++.h>using namespace std;const int N=100010;int W[N],A[N],h,B[N],lson[N],rson[N];void dfs(int x){if (x==0){return;}dfs(lson[x]);dfs(rson[x]);A[++h]=W[x];}struct Binary_Indexed_Tree{int n,bit[N];void Add(int i,int x){while (i>0){bit[i]=max(bit[i],x);i-=i&-i;}}int Query(int i){int res=0;while (i<=n){res=max(res,bit[i]);i+=i&-i;}return res;}}BIT;int main(){int n,i;scanf("%d",&n);for (i=1;i<=n;i++){scanf("%d",&W[i]);B[i]=W[i];}sort(B+1,B+1+n);int t=unique(B+1,B+1+n)-B-1;for (i=1;i<=n;i++){W[i]=lower_bound(B+1,B+1+t,W[i])-B;}for (i=1;i<=n;i++){scanf("%d%d",&lson[i],&rson[i]);}dfs(1);BIT.n=t;int Ans=1;for (i=1;i<=n;i++){int p=BIT.Query(A[i]+1);BIT.Add(A[i],p+1);Ans=max(Ans,p+1);}printf("%d\n",Ans);return 0;}
如果觉得《【牛客 - 368B】选点（dfs序 LIS 或 dfs序 + 树状数组 + 离散化 树状数组求LIS的方法）》对你有帮助，请点赞、收藏，并留下你的观点哦！
