AT_arc156_c [ARC156C] Tree and LCS

[problemUrl]: https://atcoder.jp/contests/arc156/tasks/arc156_c 頂点に $ 1 $ から $ N $ の番号がついた木 $ T $ があります。 $ T $ の $ i\ (1\leq\ i\ \leq\ N-1) $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結んでいます。 $ T $ を用いて、$ (1,2,\ldots,N) $ の順列 $ P\ =\ (P_1,P_2,\ldots,P_N) $ の**類似度**を以下で定めます。 - $ T $ 上の任意の単純パス $ x=(x_1,x_2,\ldots,x_k) $ に対して、$ y=(P_{x_1},\ P_{x_2},\ldots,P_{x_k}) $ とする。このとき、$ x $ と $ y $ の最長共通部分列の長さとして考えられる最大値を類似度とする。 類似度が最小となるような順列 $ 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 $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $

類似度が最小となるような順列 $ P $ を空白区切りで出力せよ。解が複数存在する場合、どれを出力しても正解とみなされる。

### 制約 - $ 2\ \leq\ N\ \leq\ 5000 $ - $ 1\leq\ u_i,v_i\leq\ N $ - 与えられるグラフは木 - 入力される数値は全て整数 ### Sample Explanation 1 出力例の順列の類似度は $ 1 $ となっています。これは、以下のように計算できます。 - $ x=(1) $ のとき $ y=(P_1)=(3) $ です。$ x,y $ の最長共通部分列の長さは $ 0 $ です。 - $ x=(2) $ のとき $ y=(P_2)=(2) $ です。$ x,y $ の最長共通部分列の長さは $ 1 $ です。 - $ x=(3) $ のとき $ y=(P_3)=(1) $ です。$ x,y $ の最長共通部分列の長さは $ 0 $ です。 - $ x=(1,2) $ のとき $ y=(P_1,P_2)=(3,2) $ です。$ x,y $ の最長共通部分列の長さは $ 1 $ です。 これを反転した $ x=(2,1) $ についても同様です。 - $ x=(2,3) $ のとき $ y=(P_2,P_3)=(2,1) $ です。$ x,y $ の最長共通部分列の長さは $ 1 $ です。 これを反転した $ x=(3,2) $ についても同様です。 - $ x\ =\ (1,2,3) $ のとき $ y=(P_1,P_2,P_3)=(3,2,\ 1) $ です。$ x,y $ の最長共通部分列の長さは $ 1 $ です。これを反転した $ x=(3,2,1) $ についても同様です。 類似度が $ 0 $ 以下の順列は存在しないことが証明できるので、これが答えとなります。 ### Sample Explanation 2 類似度が最小の順列が複数存在する場合、どれを出力してもよいです。例えば、`4 3 2 1` といった出力も正解になります。