C++14(g++5.4) 解法, 执行用时: 58ms, 内存消耗: 5212K, 提交时间: 2019-02-09 16:55:28

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int l[maxn],r[maxn],f[maxn],q[maxn],tot,w[maxn];
void dfs(int p){
	if(p==0)
		return ;
	q[++tot]=p;
	dfs(r[p]);
	dfs(l[p]);
}
int main(){
	int n,ans=1;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&w[i]);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&l[i],&r[i]);
	dfs(1);
	for(int i=1;i<=n;i++)
		q[i]=w[q[i]];
	f[1]=q[1];
	for(int i=2;i<=n;i++){
		if(q[i]>f[ans])
			f[++ans]=q[i];
		else{
			int pos=lower_bound(f+1,f+1+ans,q[i])-f;
			f[pos]=q[i];
		}
	}
	printf("%d\n",ans);
} 

C++11(clang++ 3.9) 解法, 执行用时: 54ms, 内存消耗: 3960K, 提交时间: 2019-02-08 21:55:33

#include<bits/stdc++.h>
using namespace std;const int N=1e5+7,inf=2e9+7;
int ls[N],rs[N],w[N],n,m,i,j,a[N],b[N],ind,tot,pos;
void dfs(int x){if(!x)return;a[++ind]=w[x];dfs(rs[x]);dfs(ls[x]);}
int main(){
	for(scanf("%d",&n),i=1;i<=n;++i)scanf("%d",w+i);
	for(i=1;i<=n;++i)scanf("%d%d",ls+i,rs+i);
	for(dfs(1),i=0;i<=n;++i)b[i]=inf;
	for(i=1;i<=n;++i){
		pos=lower_bound(b,b+tot,a[i])-b;
		b[pos]=min(b[pos],a[i]);
		tot=max(pos+1,tot);
	}printf("%d\n",tot);
}