出题人题解 | #选点#

原题解链接：https://ac.nowcoder.com/discuss/153563

$dfsdfs$序+$LISLIS$。

因为根节点的权值最小，其次是右子树的点，最后是左子树的点，所以按照先根，再右子树，再左子树的顺序$dfsdfs$整棵树，求出$dfsdfs$序，在$dfsdfs$序上求最长上升子序列。

复杂度$O(nlogn)O(nlogn)$

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 100005;
int w[N], ls[N], rs[N], q[N], f[N], tot;
void dfs(int u) {
	if (!u) return ;
	q[++tot] = u;
	dfs(rs[u]);
	dfs(ls[u]);
}
int main() {
	int n;
	scanf("%d", &n);
    if (n == 0) {
        cout << "!!!!!!!!!!1";
    }
	for (int i=1; i<=n; ++i) scanf("%d", &w[i]);
	for (int i=1; i<=n; ++i) scanf("%d%d", &ls[i], &rs[i]);
	dfs(1);
	for (int i=1; i<=n; ++i) q[i] = w[q[i]];
	int cnt = 1;
	f[1] = q[1];
	for (int i=2; i<=n; ++i) {
		if (q[i] >= f[cnt]) f[++cnt] = q[i];
		else {
			int pos = upper_bound(f + 1, f + cnt + 1, q[i]) - f;
			f[pos] = q[i];
		}
	}
	cout << cnt;
	return 0;
}