AT_abc165_f [ABC165F] LIS on Tree

[problemUrl]: https://atcoder.jp/contests/abc165/tasks/abc165_f $ N $ 頂点の木があり、$ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結んでいます。 また、頂点 $ i $ には整数 $ a_i $ が書かれています。 $ 1 $ 以上 $ N $ 以下のすべての整数 $ k $ に対して、次の問題を解いてください。 - 頂点 $ 1 $ から頂点 $ k $ までの最短パス上の頂点に書かれている整数を頂点 $ 1 $ に近い方から順に並べた数列の最長増加部分列の長さはいくつか。 なお、長さ $ L $ の数列 $ A $ の最長増加部分列とは、$ 1\ \leq\ i_1\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ : $ $ u_{N-1} $ $ v_{N-1} $

$ N $ 行出力せよ。$ k $ 行目には、頂点 $ 1 $ から頂点 $ k $ までの最短パス上の頂点に書かれている整数を頂点 $ 1 $ に近い方から順に並べた数列の最長増加部分列の長さを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ a_i\ \leq\ 10^9 $ - $ 1\ \leq\ u_i\ ,\ v_i\ \leq\ N $ - $ u_i\ \neq\ v_i $ - 与えられるグラフは木である。 - 入力はすべて整数である。 ### Sample Explanation 1 例えば、頂点 $ 1 $ から頂点 $ 5 $ までの最短パス上の頂点に書かれている整数を頂点 $ 1 $ に近い方から順に並べた数列 $ A $ は $ 1,2,5,3,4 $ です。この数列の最長増加部分列は $ A_1 $ , $ A_2 $ , $ A_4 $ , $ A_5 $ であり、この長さは $ 4 $ です。