D - LIS on Tree 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

頂点に 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 への 単純パス (あるいは単に パス) と呼びます．

制約

  • 入力される数値は全て整数
  • 2 \leq N \leq 2\times 10^5
  • 1\leq K \leq 10^{11}
  • 1\leq u_i,v_i\leq N
  • 与えられるグラフは木

入力

入力は以下の形式で標準入力から与えられる．

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 が複数存在する場合，どれを出力しても正解とみなされる．

入力例 1

5 8
1 2
2 3
2 4
4 5

出力例 1

Yes
3 2 1 4 5

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) も条件を満たします．

入力例 2

7 21
2 1
7 2
5 1
3 7
2 6
3 4

出力例 2

No

f(P) = 21 を満たす順列 P は存在しないことが証明できます．

入力例 3

8 20
3 1
3 8
7 1
7 5
3 2
6 5
4 7

出力例 3

Yes
2 1 3 5 6 8 4 7

Score: 700 points

Problem Statement

There is a tree with N vertices numbered 1 to N. The i-th edge of the tree connects vertices u_i and v_i bidirectionally.

For a permutation P=(P_1,\ldots,P_N) of (1,\ldots,N), we define f(P) as follows:

  • For each vertex i\ (1\leq i\leq N), let (v_1=1,v_2,\ldots,v_k=i) be the simple path from vertex 1 to vertex i, and let L_i be the length of a longest increasing subsequence of (P_{v_1},P_{v_2},\ldots,P_{v_k}). We define f(P) = \sum_{i=1}^N L_i.

You are given an integer K. Determine whether there is a permutation P of (1,\ldots,N) such that f(P)=K. If it exists, present one such permutation.

What is a longest increasing subsequence? A subsequence of a sequence is a sequence obtained by removing zero or more elements from the original sequence and concatenating the remaining elements without changing the order. For example, (10,30) is a subsequence of (10,20,30), but (20,10) is not.
The longest increasing subsequence of a sequence is the longest strictly increasing subsequence of that sequence.
What is a simple path? For vertices X and Y in a graph G, a walk from vertex X to vertex Y is a sequence of vertices (v_1,v_2, \ldots, v_k) such that v_1=X, v_k=Y, and v_i and v_{i+1} are connected by an edge for all 1\leq i\leq k-1. Furthermore, if v_1,v_2, \ldots, v_k are all distinct, it is called a simple path (or simply a path) from vertex X to vertex Y.

Constraints

  • All input values are integers.
  • 2 \leq N \leq 2\times 10^5
  • 1\leq K \leq 10^{11}
  • 1\leq u_i,v_i\leq N
  • The given graph is a tree.

Input

The input is given from Standard Input in the following format:

N K
u_1 v_1
\vdots
u_{N-1} v_{N-1}

Output

If there is no permutation P such that f(P)=K, print No.

If there is a permutation P such that f(P)=K, print it in the following format:

Yes
P_1 \ldots P_N

If multiple permutations P satisfy the condition, any of them will be accepted.

Sample Input 1

5 8
1 2
2 3
2 4
4 5

Sample Output 1

Yes
3 2 1 4 5

If P=(3,2,1,4,5), then f(P) is determined as follows:

  • The simple path from vertex 1 to vertex 1 is (1), and the length of the longest increasing subsequence of (P_1)=(3) is 1. Thus, L_1 = 1.

  • The simple path from vertex 1 to vertex 2 is (1,2), and the length of the longest increasing subsequence of (P_1,P_2)=(3,2) is 1. Thus, L_2 = 1.

  • The simple path from vertex 1 to vertex 3 is (1,2,3), and the length of the longest increasing subsequence of (P_1,P_2,P_3)=(3,2,1) is 1. Thus, L_3 = 1.

  • The simple path from vertex 1 to vertex 4 is (1,2,4), and the length of the longest increasing subsequence of (P_1,P_2,P_4)=(3,2,4) is 2. Thus, L_4 = 2.

  • The simple path from vertex 1 to vertex 5 is (1,2,4,5), and the length of the longest increasing subsequence of (P_1,P_2,P_4,P_5)=(3,2,4,5) is 3. Thus, L_5 = 3.

  • From the above, f(P)=1+1+1+2+3= 8.

Hence, the permutation P in the sample output satisfies the condition f(P)=8. Besides, P=(3,2,4,5,1) also satisfies the condition, for example.

Sample Input 2

7 21
2 1
7 2
5 1
3 7
2 6
3 4

Sample Output 2

No

It can be proved that no permutation P satisfies f(P) = 21.

Sample Input 3

8 20
3 1
3 8
7 1
7 5
3 2
6 5
4 7

Sample Output 3

Yes
2 1 3 5 6 8 4 7