← 返回题目列表

AtCoder · arc175_d

D. 树 2 上的 LIS

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

有一棵树 N 顶点编号 1 to N。的 i树的第一条边连接顶点 u_i 和 v_i 双向。

对于排列 P=(P_1,\ldots,P_N) of (1,\ldots,N),我们定义 f(P) 如下:

  • 对于每个顶点 路径图的 i\ (1\leq i\leq N),让 (v_1=1,v_2,\ldots,v_k=i) 是从顶点开始的简单路径 1 到顶点 i,让 L_i 是最长递增子序列的长度 (P_{v_1},P_{v_2},\ldots,P_{v_k})。我们定义 f(P) = \sum_{i=1}^N L_i.

给你一个整数 K。判断是否存在排列 P of (1,\ldots,N) 这样 f(P)=K。如果存在,请提出一种这样的排列。

什么是最长递增子序列? 序列的 A 子序列 是通过从原始序列中删除零个或多个元素并将剩余元素连接起来而不改变顺序而获得的序列。 例如, (10,30) 是以下序列的子序列 (10,20,30),但是 (20,10) 不是。
的 最长递增子序列 序列的 是该序列的最长严格递增子序列。
什么是简单路径? 对于顶点 图表中的 X 和 Y 在图表中 G,一个 步行 从顶点 X 到顶点 Y 是一系列顶点 (v_1,v_2, \ldots, v_k) 这样 v_1=X, v_k=Y,和 v_i 和 v_{i+1} 通过一条边连接所有 1\leq i\leq k-1。 此外,如果 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}

输出

如果没有排列 P 这样 f(P)=K,打印 No.

如果有排列 P 这样 f(P)=K,按以下格式打印:

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

If P=(3,2,1,4,5),然后 f(P) 确定如下:

  • 从顶点开始的简单路径 1 到顶点 1 is (1),以及最长递增子序列的长度 (P_1)=(3) is 1。因此, L_1 = 1.

  • 从顶点开始的简单路径 1 到顶点 2 is (1,2),以及最长递增子序列的长度 (P_1,P_2)=(3,2) is 1。因此, L_2 = 1.

  • 从顶点开始的简单路径 1 到顶点 3 is (1,2,3),以及最长递增子序列的长度 (P_1,P_2,P_3)=(3,2,1) is 1。因此, L_3 = 1.

  • 从顶点开始的简单路径 1 到顶点 4 is (1,2,4),以及最长递增子序列的长度 (P_1,P_2,P_4)=(3,2,4) is 2。因此, L_4 = 2.

  • 从顶点开始的简单路径 1 到顶点 5 is (1,2,4,5),以及最长递增子序列的长度 (P_1,P_2,P_4,P_5)=(3,2,4,5) is 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

可以证明没有排列 P 满足 f(P) = 21.


示例输入 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