P17145 [NOI 2026] 彩虹树

题面、样例附件来自 [QOJ](https://qoj.ac/contest/3939/problem/18988)。 提交到洛谷上时，无需引用头文件 `#include "rainbow.h"`。直接将 ```cpp int rainbow(int c, int n, std::vector f); ``` 复制到程序开头，同时选用 C++17 或者更高版本编译器编译。

传说在夜之国中，有一棵包含 $n$ 个结点的彩虹树。彩虹树是一棵有根树，结点编号为 $0\sim n-1$，其中结点 $0$ 是彩虹树的树根，结点 $i$（$1\le i

### 【实现细节】 选手不需要，也不应该实现 `main` 函数。 选手需要确保提交的程序源文件包含头文件 `rainbow.h`，即在程序开头加入以下代码： ```cpp #include "rainbow.h" ``` 选手需要在提交的程序源文件 `rainbow.cpp` 中实现以下函数： ```cpp int rainbow(int c, int n, std::vector f); ``` - $c,n$ 分别表示测试点编号与彩虹树的结点数。$c=0$ 表示该测试点为样例。 - $f$ 是一个长度为 $n$ 的序列，其中 $f_0=0$，$f_i$（$1\le i

### 【测试程序方式】 选手可以在本题目录下使用如下命令编译得到可执行文件： ```bash g++ grader.cpp rainbow.cpp -o rainbow -O2 -std=c++14 -static ``` 对于编译得到的可执行文件 `rainbow`： - 可执行文件将从标准输入读入以下格式的数据： - 第一行包含两个非负整数 $c,n$。 - 第二行包含 $n-1$ 个非负整数 $f_1,f_2,\ldots,f_{n-1}$。 - 可执行文件将输出以下格式的数据至标准输出： - 输出一行一个非负整数，表示 `rainbow` 函数的返回值。

### 【样例 $1$ 解释】 - 满足规律 $S=\varnothing$ 的彩虹树的缤纷度共有 $[1,1,1]$、$[2,1,1]$、$[3,1,1]$ 三种。 - 满足规律 $S=\{1\}$ 的彩虹树的缤纷度共有 $[1,1,1]$、$[2,1,1]$ 两种。 - 满足规律 $S=\{2\}$ 的彩虹树的缤纷度共有 $[1,1,1]$、$[2,1,1]$ 两种。 - 满足规律 $S=\{1,2\}$ 的彩虹树的缤纷度有 $[1,1,1]$ 一种。 因此答案为 $3+2+2+1=8$。 ### 【样例 $3$】 见选手目录下的 `rainbow/rainbow3.in` 与 `rainbow/rainbow3.ans`。 该样例满足测试点 $3,4$ 的约束条件。 ### 【样例 $4$】 见选手目录下的 `rainbow/rainbow4.in` 与 `rainbow/rainbow4.ans`。 该样例满足测试点 $5\sim7$ 的约束条件。 ### 【样例 $5$】 见选手目录下的 `rainbow/rainbow5.in` 与 `rainbow/rainbow5.ans`。 该样例满足测试点 $8,9$ 的约束条件。 ### 【样例 $6$】 见选手目录下的 `rainbow/rainbow6.in` 与 `rainbow/rainbow6.ans`。 该样例满足测试点 $10\sim12$ 的约束条件。 ### 【数据范围】 对于所有测试数据，均有： - $1\le n\le200$； - 对于所有 $1\le i