Background

The statement and sample attachments come from QOJ。

When submitting to Luogu, you do not need to include the header #include "rainbow.h"。Just copy

int rainbow(int c, int n, std::vector<int> f);

to the beginning of your program, and compile with a C++17 or higher compiler。

Problem Description

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$。

Input Format

【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:

#include "rainbow.h"

Contestants need to implement the following function in the submitted program source file rainbow.cpp:

int rainbow(int c, int n, std::vector<int> 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。

Output Format

【Grader program mode】

Contestants can compile an executable file in this problem directory using the following command:

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。

0 3
0 0

8

0 6
0 1 0 3 1

279

Hint

【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