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 翻译