P17145 [NOI 2026] Rainbow Tree

The statement and sample attachments come from [QOJ](https://qoj.ac/contest/3939/problem/18988)。 When submitting to Luogu, you do not need to include the header `#include "rainbow.h"`。Just copy ```cpp int rainbow(int c, int n, std::vector f); ``` to the beginning of your program, and compile with a C++17 or higher compiler。

Legend says that in the Kingdom of Night, there is a Rainbow Tree with $n$ nodes。The Rainbow Tree is a rooted tree with nodes numbered from $0 \sim n-1$。Node $0$ is the root of the Rainbow Tree, and the parent of node $i$ ($1 \le i < n$) is $f_i$。 Each node on the Rainbow Tree can display any color。There are infinitely many colors, but the **colorfulness** of the Rainbow Tree depends only on the **number of distinct colors that appear** in each subtree, and does not depend on which colors they are。Specifically, let the subtree rooted at node $i$ ($0 \le i < n$) contain $c_i$ distinct colors among its nodes。Then the colorfulness of the Rainbow Tree can be represented by the sequence $[c_0, c_1, \ldots, c_{n-1}]$。 For example, in the figure below, nodes $0, 1, 5$ are blue, nodes $2, 4$ are red, and node $3$ is yellow, so the colorfulness of the Rainbow Tree is $[3,2,1,2,1,1]$。 :::align{center}  ::: Changes in the clouds cause the colors of the Rainbow Tree to follow certain specific rules。Each rule can be described by a corresponding subset of nodes $S \subseteq \{1,2,\ldots,n-1\}$：for every node $u$ in set $S$, the color of $u$ must be the same as the color of some ancestor。Formally, for all $u \in S$, there exists an ancestor $p$ of $u$ ($p \ne u$) such that $u$ and $p$ have the same color。 Even with the restriction above, the Rainbow Tree can still display different colorings, producing different colorfulness sequences。Let $w_S$ be the **number of distinct kinds** of colorfulness sequences of Rainbow Trees that satisfy rule $S$。Two colorfulness sequences are considered different if and only if at least one element differs between the two sequences。 Compute, for all possible $2^{n-1}$ rules, the sum of the numbers of kinds of colorfulness sequences under each rule, i.e. $\sum_{S \subseteq \{1,2,\ldots,n-1\}} w_S$。Since the answer may be large, output the result modulo $998244353$。

### 【Implementation details】 Contestants do not need to, and should not, implement the `main` function。 Contestants need to ensure that the submitted program source file includes the header `rainbow.h`, i.e. add the following code at the beginning of the program: ```cpp #include "rainbow.h" ``` Contestants need to implement the following function in the submitted program source file `rainbow.cpp`: ```cpp int rainbow(int c, int n, std::vector f); ``` - $c, n$ represent the test point ID and the number of nodes of the Rainbow Tree, respectively。$c = 0$ means this test point is the sample。 - $f$ is a sequence of length $n$, where $f_0 = 0$ and $f_i$ ($1 \le i < n$) is the parent of node $i$。 - This function should return the sum, over all rules, of the number of kinds of colorfulness sequences modulo $998244353$。 - For each test point, this function will be called exactly once by the grader。 `template_rainbow.cpp` in this problem directory is the provided sample code。Contestants may refer to it and implement their own code。

### 【Grader program mode】 Contestants can compile an executable file in this problem directory using the following command: ```bash g++ grader.cpp rainbow.cpp -o rainbow -O2 -std=c++14 -static ``` For the compiled executable file `rainbow`: - The executable will read data from standard input in the following format: - The first line contains two non-negative integers $c, n$。 - The second line contains $n-1$ non-negative integers $f_1, f_2, \ldots, f_{n-1}$。 - The executable will output data to standard output in the following format: - Output one line with one non-negative integer, which is the return value of the `rainbow` function。

### 【Sample $1$ explanation】 - For rule $S = \varnothing$, there are three possible colorfulness sequences: $[1,1,1]$, $[2,1,1]$, $[3,1,1]$。 - For rule $S = \{1\}$, there are two possible colorfulness sequences: $[1,1,1]$, $[2,1,1]$。 - For rule $S = \{2\}$, there are two possible colorfulness sequences: $[1,1,1]$, $[2,1,1]$。 - For rule $S = \{1,2\}$, there is one possible colorfulness sequence: $[1,1,1]$。 Therefore, the answer is $3+2+2+1=8$。 ### 【Sample $3$】 See `rainbow/rainbow3.in` and `rainbow/rainbow3.ans` in the contestants’ directory。 This sample satisfies the constraints of test points $3,4$。 ### 【Sample $4$】 See `rainbow/rainbow4.in` and `rainbow/rainbow4.ans` in the contestants’ directory。 This sample satisfies the constraints of test points $5 \sim 7$。 ### 【Sample $5$】 See `rainbow/rainbow5.in` and `rainbow/rainbow5.ans` in the contestants’ directory。 This sample satisfies the constraints of test points $8, 9$。 ### 【Sample $6$】 See `rainbow/rainbow6.in` and `rainbow/rainbow6.ans` in the contestants’ directory。 This sample satisfies the constraints of test points $10 \sim 12$。 ### 【Constraints】 For all testdata: - $1 \le n \le 200$； - For all $1 \le i < n$, $0 \le f_i < i$。 ::cute-table{tuack} | Test point ID | $n \le$ | Special property | |:-:|:-:|:-:| | $1$ | $4$ | None | | $2$ | $8$ | ^ | | $3,4$ | $16$ | ^ | | $5 \sim 7$ | $50$ | ^ | | $8,9$ | $10^2$ | $B$ | | $10 \sim 12$ | ^ | None | | $13 \sim 15$ | $150$ | ^ | | $16$ | $200$ | $A$ | | $17 \sim 19$ | ^ | $B$ | | $20 \sim 25$ | ^ | None | Special property $A$: For all $1 \le i < n$, $f_i = i-1$。 Special property $B$: For all $0 \le i < n$, there are at most two $j$ such that $f_j = i$。 Translated by ChatGPT 5