AT_arc175_d [ARC175D] LIS on Tree 2

[problemUrl]: https://atcoder.jp/contests/arc175/tasks/arc175_d 頂点に $ 1 $ から $ N $ の番号がついた $ N $ 頂点の木があります．木の $ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を双方向に結んでいます． $ (1,\ldots,N) $ の順列 $ P=(P_1,\ldots,P_N) $ に対し $ f(P) $ を以下で定めます． - 頂点 $ i\ (1\leq\ i\leq\ N) $ に対し，頂点 $ 1 $ から頂点 $ i $ への単純パスを $ (v_1=1,v_2,\ldots,v_k=i) $ として，$ (P_{v_1},P_{v_2},\ldots,P_{v_k}) $ の最長増加部分列の長さを $ L_i $ とする．$ f(P)\ =\ \sum_{i=1}^N\ L_i $ と定める． 整数 $ K $ が与えられます．$ f(P)=K $ を満たす $ (1,\ldots,N) $ の順列 $ P $ が存在するか判定し，存在する場合は一つ示してください． 最長増加部分列とは 数列の**部分列**とは，数列から $ 0 $ 個以上の要素を取り除いた後，残りの要素を元の順序で連結して得られる数列のことをいいます． 例えば，$ (10,30) $ は $ (10,20,30) $ の部分列ですが，$ (20,10) $ は $ (10,20,30) $ の部分列ではありません． 数列の**最長増加部分列**とは，数列の狭義単調増加な部分列の中で列の長さが最大のものを指します． 単純パスとは グラフ $ G $ 上の頂点 $ X,Y $ に対して，頂点列 $ (v_1,v_2,\ \ldots,\ v_k) $ であって， $ v_1=X $, $ v_k=Y $ かつ，$ 1\leq\ i\leq\ k-1 $ に対して $ v_i $ と $ v_{i+1} $ が辺で結ばれているようなものを頂点 $ X $ から頂点 $ Y $ への **ウォーク** と呼びます． さらに，$ v_1,v_2,\ \ldots,\ v_k $ がすべて異なるようなものを頂点 $ X $ から頂点 $ Y $ への **単純パス** (あるいは単に **パス**) と呼びます．

入力は以下の形式で標準入力から与えられる． > $ N $ $ K $ $ u_1 $ $ v_1 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $

$ f(P)=K $ を満たす順列 $ P $ が存在しない場合， `No` を出力せよ． $ f(P)=K $ を満たす順列 $ P $ が存在する場合，以下の形式で出力せよ． > Yes $ P_1 $ $ \ldots $ $ P_N $ 条件を満たす順列 $ P $ が複数存在する場合，どれを出力しても正解とみなされる．

### 制約 - 入力される数値は全て整数 - $ 2\ \leq\ N\ \leq\ 2\times\ 10^5 $ - $ 1\leq\ K\ \leq\ 10^{11} $ - $ 1\leq\ u_i,v_i\leq\ N $ - 与えられるグラフは木 ### Sample Explanation 1 $ P=(3,2,1,4,5) $ のとき，$ f(P) $ は以下のように定まります． - 頂点 $ 1 $ から頂点 $ 1 $ への単純パスは $ (1) $ であり，$ (P_1)=(3) $ の最長増加部分列の長さは $ 1 $ である．よって $ L_1\ =\ 1 $ である． - 頂点 $ 1 $ から頂点 $ 2 $ への単純パスは $ (1,2) $ であり，$ (P_1,P_2)=(3,2) $ の最長増加部分列の長さは $ 1 $ である．よって $ L_2\ =\ 1 $ である． - 頂点 $ 1 $ から頂点 $ 3 $ への単純パスは $ (1,2,3) $ であり，$ (P_1,P_2,P_3)=(3,2,1) $ の最長増加部分列の長さは $ 1 $ である．よって $ L_3\ =\ 1 $ である． - 頂点 $ 1 $ から頂点 $ 4 $ への単純パスは $ (1,2,4) $ であり，$ (P_1,P_2,P_4)=(3,2,4) $ の最長増加部分列の長さは $ 2 $ である．よって $ L_4\ =\ 2 $ である． - 頂点 $ 1 $ から頂点 $ 5 $ への単純パスは $ (1,2,4,5) $ であり，$ (P_1,P_2,P_4,P_5)=(3,2,4,5) $ の最長増加部分列の長さは $ 3 $ である．よって $ L_5\ =\ 3 $ である． - 以上より，$ f(P)=1+1+1+2+3=\ 8 $ である． このことから，出力例の $ P $ は $ f(P)=8 $ という条件を満たすことが分かります．この他にも，例えば $ P=(3,2,4,5,1) $ も条件を満たします． ### Sample Explanation 2 $ f(P)\ =\ 21 $ を満たす順列 $ P $ は存在しないことが証明できます．