选点

题目地址：

https://ac.nowcoder.com/acm/problem/22494

基本思路:

我们看到题目给出的条件,
要满足这个条件我们可以考虑构造序的访问顺序,
我们知道对于一棵子树来说根节点肯定是第一个访问的,
那么只要我们先访问右子树再访问左子树,用这样的顺序去构造序列,
那么生成的这个序列的就是我们的答案了。

参考代码:

#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define ll long long
#define ull unsigned long long
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define debug(x) cerr << #x << " = " << x << '\n';
#define pll pair <ll, ll>
#define fir first
#define sec second
#define INF (int)3e9
#define int ll

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 1e5 + 10;
int n,w[maxn],a[maxn];
vector<int> G[maxn];
vector<int> vec;
signed main() {
  n = read();
  rep(i, 1, n) w[i] = read();
  for (int i = 1; i <= n; i++) {
    int l = read(), r = read();
    if (r) G[i].push_back(r);
    if (l) G[i].push_back(l);
  }
  function<void(int)> dfs = [&dfs](int u) {
      vec.push_back(w[u]);
      for (auto &to : G[u]) dfs(to);
  };
  dfs(1);
  vector<int> dp(SZ(vec), INF);
  for (int i = 0; i < SZ(vec); i++) {
    *lower_bound(all(dp), vec[i]) = vec[i];
  }
  int ans = lower_bound(all(dp), INF) - dp.begin();
  print(ans);
  return 0;
}