[ARC175] D - LIS on Tree 2

D - LIS on Tree 2

Time Limit: 2 sec / Memory Limit: 1024 MB

题面

有一棵包含 个顶点、编号从 到 的树。树的第 条边连接顶点 和 。

对于一个由 的排列 ，定义 如下：

• 对于每个顶点 ，设 是从顶点 到顶点 的简单路径， 是序列 的最长递增子序列的长度。我们定义 。

给定一个整数 。判断是否存在一个排列 ，使得 。如果存在，给出这样一个排列。

什么是最长递增子序列？一个序列的子序列是通过从原序列中移除零个或多个元素，并将剩余元素连接而不改变顺序得到的序列。例如， 是 的一个子序列，但 不是。
一个序列的最长递增子序列是该序列中最长的严格递增子序列。
什么是简单路径？对于图 中的顶点 和 ，从顶点 到顶点 的路径是一系列顶点 ，满足 ，，并且对于所有 ， 和 是由一条边连接的。此外，如果 都是不同的，则称之为简单路径（或简称路径）。

限制条件

• 所有输入值均为整数。
• 给定的图是一棵树。

---

输入

输入以以下格式从标准输入给出：

输出

如果不存在一个排列 满足 ，则输出 No。

如果存在一个排列 满足 ，则以以下格式输出：

Yes

如果有多个满足条件的排列 ，任何一个都将被接受。

---

输入样例 1

5 8
1 2
2 3
2 4
4 5

输出样例 1

Yes
3 2 1 4 5

如果 ，则 的计算如下：

• 从顶点 到顶点 的简单路径是 ，序列 的最长递增子序列的长度为 。因此，。

• 从顶点 到顶点 的简单路径是 ，序列 的最长递增子序列的长度为 。因此，。

• 从顶点 到顶点 的简单路径是 ，序列 的最长递增子序列的长度为 。因此，。

• 从顶点 到顶点 的简单路径是 ，序列 的最长递增子序列的长度为 。因此，。

• 从顶点 到顶点 的简单路径是 ，序列 的最长递增子序列的长度为 。因此，。

• 综上，。

因此，样例输出中给出的排列 满足条件 。此外， 也满足条件，作为另一个例子。

---

输入样例 2

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

输出样例 2

No

可以证明没有任何排列 满足 。

---

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