9479

P9479 [NOI 2023] 桂花树 好题！ 可以先看看这个，虽然感觉并没有什么用（ 先考虑第一条限制。 在纸上画几个图，大概可以分成以下几类（左边是原树，右边是有 \(n+m\) 个点的新树）： 黑色点表示原树上的点，蓝色点表示新加入的点。 上面三个图分别代表：新点挂在原树的一个点上成为叶节点 ......

显然， - 条件一等价于在 $T'$ 中，$1\sim n$ 组成的虚树等于它本身。 - 条件二等价于 $1\sim i$ 组成的虚树上点的标号不超过 $i+k$。 我们考虑在原树的基础上依次添加 $n+1\sim n+m$ 这 $m$ 个点。添加一个点 $i$ 时，它与原树的位置关系可能有以下几种 ......