P6653 [YsOI2020] 造林

「承前」 Ysuperman 响应号召，决定在幼儿园外造林。 呐呐，如果这样的话，Ysuperman 便能在这炎热的夏天与小朋友们玩游戏了呢。

为了落实环保工作，Ysuperman 购进了一批树，它们都长一个样。由于树还没有种下去，所以这些树还没有根，可以认为是**无根树**。 Ysuperman 觉得全都种长得一样的树太无聊了，于是 TA 请到了园艺公司帮 TA 规划。园艺公司提供给了 TA 一个方法——「嫁接」。 下面给出「嫁接」操作的定义： 定义「叶子节点」为树上度数为 $1$ 的节点。 「嫁接」操作指：在一棵**无根树**上接入一个新的「叶子节点」。 例如：  图 2 是由图 1 的树进行一次合法的嫁接操作后得到的树，图 3 也是由图 1 的树进行一次合法的嫁接操作后得到的树。 那么，我们还知道，树有一个基本属性：「品种」。 一棵树的「品种」是指**每个点的最大子树大小所构成的可重集**。 两棵树的「品种」不同，当且仅当**每个点的最大子树大小所构成的可重集不同**。 这里的一个点的**最大子树大小**指将这个点删掉后**最大的联通块所包含的点数**。 例如：  图 4 的树的每个点的最大子树大小所构成的可重集为：$ \{ 2,2,3,3 \} $ 图 5 的树的每个点的最大子树大小所构成的可重集为：$ \{ 2,2,3,3 \} $ 图 6 的树的每个点的最大子树大小所构成的可重集为：$ \{ 1,3,3,3 \} $ 所以说，图 4 的树与图 5 的树「品种」相同，与图 6 的树「品种」不同。 Ysuperman 想知道，通过一次「嫁接」操作，可以构造出的树包含多少不同的「品种」，以及对于每个「品种」，有多少不同的「嫁接」方法可以构造。请**从小到大**输出每个「品种」的「嫁接」方法数。 两个「嫁接」方案不同，当且仅当在「嫁接」操作中与新接入的「叶子节点」直接相连的点不同。

无

无

**本题采用捆绑测试。** ### 样例解释 1 可以构造出 1 种「品种」为 $\{2,4,4,5,5,5\}$ 的树。 可以构造出 2 种「品种」为 $\{3,3,4,5,5,5\}$ 的树。 可以构造出 2 种「品种」为 $\{3,3,4,4,5,5\}$ 的树。 ### 样例解释 2 可以构造出 1 种「品种」为 $\{3,5,5,7,7,7,7,7\}$ 的树。 可以构造出 2 种「品种」为 $\{4,4,5,7,7,7,7,7\}$ 的树。 可以构造出 4 种「品种」为 $\{4,4,5,6,7,7,7,7\}$ 的树。 对于 100% 的数据，满足 $1 \le n\le2\cdot 10^6$。 定义「链」为所有节点度数不超过 $2$ 的树。 定义「菊花」为包含 $n-1$ 个「叶子节点」的树。 特殊性质 1：保证树的形态为一条「链」。 特殊性质 2：保证树的形态为一朵「菊花」。 特殊性质 3：保证树的形态为一棵完全二叉树。 | subtask | $n$ | 特殊性质 | 分值 | 时间限制 | | :-----------: | :-----------: | :-----------: | :--------:| :---------:| | 1 | $\le 2\cdot 10^6$ | 2 | 2 | 4s | | 2 | $\le 2\cdot 10^6$ | 1 | 3 | 4s | | 3 | $\le 300$ | 无 | 5 | 1s | | 4 | $\le 2\cdot10^6$ | 3 | 7 | 4s | | 5 | $\le 5000$ | 无 | 23 | 1s | | 6 | $\le 5\cdot10^4$ | 无 | 29 | 2s | | 7 | $\le 2\cdot10^6$ | 无 | 31 | 4s | ### 提示： 如果你不知道完全二叉树是什么意思，Ysuperman 提供了一个链接：[Link](https://zh.wikipedia.org/zh/%E4%BA%8C%E5%8F%89%E6%A0%91#%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91)。 输入输出较大，请使用较快的输入输出方式。 如果您使用了所需栈空间较大的递归算法，可以在本地（NOI linux 下）先使用 ```sudo su``` 获取权限，再使用 ```ulimit -s unlimited ``` 命令开启无限栈。 题目并不难。