【每日一题】dfs序专题 选点

Description

Solution

前置知识：最长上升子序列O(nlogn)的贪心做法, dfs序
分析:从题目中可以得出，根 < 右子树 < 左子树，如果要选择最多的点，那么如果能够处理出根 -> 右子树 -> 左子树的dfs序，在序列上取一个最长上升子序列，就能选到最多的点，于是长度即为答案。
时间复杂度：O(nlogn)

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
int w[N], seq[N], tot;
vector<int> G[N];
void dfs(int u, int par) {
  seq[++tot] = w[u];
  for(auto &x : G[u]) {
    dfs(x, u);
  }
}
int len, f[N];
int main() {
  int n; cin >> n;
  for(int i = 1 ; i <= n; i++) {
    cin >> w[i];
  }
  for(int i = 1; i <= n; i++) {
    int l, r; cin >> l >> r;
    if(r) G[i].emplace_back(r);
    if(l) G[i].emplace_back(l);
  }
  dfs(1, -1);
  f[++len] = w[1];
  for(int i = 2; i <= tot; i++) {
    if(f[len] < seq[i]) {
      f[++len] = seq[i];
    } else {
      f[lower_bound(f + 1, f + 1 + len, seq[i]) - f] = seq[i];
    }
  }
  cout << len << "\n";
  return 0;
}