桂花树

[NOI2023] 桂花树 题目描述 小 B 八年前看到的桂花树是一棵 \(n\) 个节点的树 \(T\)，保证 \(T\) 的非根结点的父亲的编号小于自己。给定整数 \(k\)，称一棵 \((n+m)\) 个节点的有根树 \(T^{\prime}\) 是繁荣的，当且仅当以下所有条件满足： 对于任意 ......

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

称编号 \(> n\) 的点为新点。 由条件 1 可以推出树 \(T\) 为结点 \(1 \sim n\) 在树 \(T'\) 上的 虚树。 由条件 2 可以推出 \(\forall 1 \le u < v \le n + m, \operatorname{lca}(u, v) \le v + k\ ......

### $k=0$ 考试时脑抽，现在想一想感觉挺简单的。 从小到大依次加点，那么题目的条件等价于每次可以把点加在一条边中间，或者加入一个叶子，并且这两种方式都会导致下一个点加入时可选的方案加二。 把方案数乘起来就好了。 ### $k>0$ 需要一点观察。 除了上述两种加点的方式，还存在一种方式是，选 ......

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