题干：
 

有一棵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

输入

5
1 5 4 2 3
3 2
4 5
0 0
0 0
0 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 second
using 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;
}