AtCoder Beginner Contest 165 F問題 - LIS on Tree

Source

AtCoder Beginner Contest 165
問題文

問題概要

省略

解法

省略

cLay（version 20210607-1）のコード

C++に変換後のコードはこちら

int N, A[2d5], U[], V[];
int res[];
int sz, arr[];
graph g;

void solve(int n){
  int k, bval;

  k = lower_bound(arr, arr+sz, A[n]) - arr;
  bval = if[k==sz, -1, arr[k]];
  arr[k] = A[n];
  if(k==sz) sz++;

  res[n] = sz;
  rep[g.edge[n]](i,g.es[n]) solve(i);

  if(bval==-1) sz--;
  else         arr[k] = bval;
}

{
  rd(N,A(N),(U--,V--)(N-1));
  g.setEdgeRootedTree(N,N-1,U,V);
  solve(0);
  wtLn(res(N));
}

Current time: 2024年04月26日02時40分04秒
Last modified: 2021年06月07日22時47分55秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC165 ABC_F
トップページに戻る

Logged in as: unknown user (not login)