AT_arc175_d.[ARC175D] LIS on Tree 2

有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。树的第 $i$ 条边连接了顶点 $u_i$ 和顶点 $v_i$，且为双向边。

对于 $1$ 到 $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$，请判断是否存在一个排列 $P$ 使得 $f(P)=K$，如果存在，请给出一个这样的排列。

最长递增子序列的定义
数列的子序列是指从原数列中删除 $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$ $K$
$u_1$ $v_1$
$\vdots$
$u_{N-1}$ $v_{N-1}$

如果不存在满足 $f(P)=K$ 的排列 $P$，输出 No。

如果存在满足 $f(P)=K$ 的排列 $P$，输出如下格式：

Yes $P_1$ $P_2$ $\ldots$ $P_N$

如果有多个满足条件的排列 $P$，输出任意一个均可。

数据范围

• 输入的所有数均为整数。
• $2\leq N\leq 2\times 10^5$
• $1\leq K\leq 10^{11}$
• $1\leq u_i,v_i\leq N$
• 给定的图保证是一棵树。

样例解释 1

当 $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

可以证明不存在满足 $f(P)=21$ 的排列 $P$。

由 ChatGPT 4.1 翻译