P6862 [RC-03] 随机树生成器
题目描述
小 R 有一个随机树生成器，其工作原理如下：
- 输入 $n$，则对于每个 $1
输入格式
无
输出格式
无
说明/提示
【样例说明】
- 数据 $1$：一共有两种情况，$1$ 号点的度数分别为 $1,2$。因此答案为 $3$。
- 数据 $2$：一共有两种情况，$2$ 号点的度数分别为 $1,2$。因此答案为 $3$。
- 数据 $3$：一共有两种情况，$3$ 号点的度数均为 $1$。因此答案为 $2$。
【数据范围】
本题捆绑测试。
对于 $100\%$ 的数据，$1\le T\le 10^5$，$1\le k\le n\le 10^7$。详细数据范围如下。
- Subtask 1（20 分）：$T\le 50$，$n\le 8$。
- Subtask 2（55 分）：$T=1$，$n\le 10^5$。
- Subtask 3（20 分）：$T=1$。
- Subtask 4（5 分）：没有任何附加限制。