AtCoder Beginner Contest 165F問題

ABC165F

解法

• Sub: LIS(line 型)
• Main: LIS(Tree 型)

Line 型の LIS が解けていれば，それを tree 型にするのは容易． DP 配列を DFS で使い和ます． 注意は，遷移から戻るときに DP 配列を元に戻すこと．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n,m; cin >> n; m = n-1;

  vll a(n); cinv(a);

  vvll to(n);

  rep(i,m){

    ll a, b; cin >> a >> b;

    --a, --b;

    to[a].push_back(b);

    to[b].push_back(a);

  }

  vll dp(n, INFL);

  vll ans(n);

  auto dfs = [&](auto f, ll cu, ll pa = -1) -> void {

    auto it = lower_bound(all(dp), a[cu]);

    ll tmp = *it;

    *it = a[cu];

    for(auto ne: to[cu]) if(ne != pa){

      f(f, ne, cu);

    }

    auto it2 = lower_bound(all(dp), INFL);

    ans[cu] = it2 - dp.begin();

    *it = tmp;    

  };

  dfs(dfs, 0);

  for(auto i: ans){

    cout << i << endl;

  }

  return 0;

}