/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
頂点に 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 への 単純パス (あるいは単に パス) と呼びます。制約
- 2 \leq N \leq 5000
- 1\leq u_i,v_i\leq N
- 与えられるグラフは木
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
出力
類似度が最小となるような順列 P を空白区切りで出力せよ。解が複数存在する場合、どれを出力しても正解とみなされる。
入力例 1
3 1 2 2 3
出力例 1
3 2 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 以下の順列は存在しないことが証明できるので、これが答えとなります。
入力例 2
4 2 1 2 3 2 4
出力例 2
3 4 1 2
類似度が最小の順列が複数存在する場合、どれを出力してもよいです。例えば、4 3 2 1 といった出力も正解になります。
Score : 600 points
Problem Statement
We have a tree T with vertices numbered 1 to N. The i-th edge of T connects vertex u_i and vertex v_i.
Let us use T to define the similarity of a permutation P = (P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) as follows.
- For a simple path x=(x_1,x_2,\ldots,x_k) in T, let y=(P_{x_1}, P_{x_2},\ldots,P_{x_k}). The similarity is the maximum possible length of a longest common subsequence of x and y.
Construct a permutation P with the minimum similarity.
What is a subsequence?
A subsequence of a sequence is a sequence obtained by removing zero or more elements from that sequence and concatenating the remaining elements without changing the relative order. For instance, (10,30) is a subsequence of (10,20,30), but (20,10) is not.What is a simple path?
For vertices X and Y in a graph G, a walk from X to Y is a sequence of vertices v_1,v_2, \ldots, v_k such that v_1=X, v_k=Y, and there is an edge connecting v_i and v_{i+1}. A simple path (or simply a path) is a walk such that v_1,v_2, \ldots, v_k are all different.Constraints
- 2 \leq N \leq 5000
- 1\leq u_i,v_i\leq N
- The given graph is a tree.
- All numbers in the input are integers.
Input
The input is given from Standard Input in the following format:
N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
Output
Print a permutation P with the minimum similarity, separated by spaces. If multiple solutions exist, you may print any of them.
Sample Input 1
3 1 2 2 3
Sample Output 1
3 2 1
This permutation has a similarity of 1, which can be computed as follows.
-
For x=(1), we have y=(P_1)=(3). The length of a longest common subsequence of x and y is 0.
-
For x=(2), we have y=(P_2)=(2). The length of a longest common subsequence of x and y is 1.
-
For x=(3), we have y=(P_2)=(1). The length of a longest common subsequence of x and y is 0.
-
For x=(1,2), we have y=(P_1,P_2)=(3,2). The length of a longest common subsequence of x and y is 1. The same goes for x=(2,1), the reversal of (1,2).
-
For x=(2,3), we have y=(P_2,P_3)=(2,1). The length of a longest common subsequence of x and y is 1. The same goes for x=(3,2), the reversal of (2,3).
-
For x=(1,2,3), we have y=(P_1,P_2,P_3)=(3,2,1). The length of a longest common subsequence of x and y is 1. The same goes for x=(3,2,1), the reversal of (1,2,3).
We can prove that no permutation has a similarity of 0 or less, so this permutation is a valid answer.
Sample Input 2
4 2 1 2 3 2 4
Sample Output 2
3 4 1 2
If multiple permutations have the minimum similarity, you may print any of them. For instance, you may also print 4 3 2 1.