F - LIS on Tree

[Q] https://atcoder.jp/contests/abc165/tasks/abc165_f
タイトル通りとは恐れ入った。
dfs + LIS。

DPをdfsごとにvector<ll>でコピーするとTLE。
バックトラックで使いまわす必要があるかも。

Q. LIS？
A. https://atcoder.jp/contests/typical90/tasks/typical90_bh
これをすでにテンプレート化していたので、あてはめるだけ。

ll A[200010];
ll N;
vector<ll> G[200010];
ll ans[200010];
ll DP[200010];

void dfs(ll d, ll pre, ll cnt){
 ll pos = lower_bound(DP, DP+cnt, A[d]) - DP;
 ll preval = DP[pos];
 DP[pos] = A[d]; // バックトラック
 if (pos==cnt) ++cnt;
 ans[d] = cnt;
 for(auto v: G[d]){
   if (v == pre) continue;
   dfs(v, d, cnt);
 }
 DP[pos]=preval; // 復元
}

int main(){
 cincout();
 
 cin >> N;
 vector<ll> DP;
 rep(i, N) cin >> A[i];
 rep(i, N-1){
   ll u, v;
   cin >> u >> v;
   --u, --v;
   G[u].push_back(v);
   G[v].push_back(u);
 }
 dfs(0, -1, 0);
 rep(i, N) cout << ans[i] << endl;
}