Có một cây có gốc gồm \(n\) đỉnh, đánh số từ \(0\) đến \(n-1\). Đỉnh \(0\) là gốc; với \(1\le i<n\), cha của đỉnh \(i\) là \(f_i\).

Mỗi đỉnh có thể mang một trong vô hạn màu. Với mỗi đỉnh \(i\), gọi \(c_i\) là số màu khác nhau xuất hiện trong cây con gốc \(i\). Độ rực rỡ của cây là dãy

Độ rực rỡ chỉ phụ thuộc vào số màu phân biệt trong các cây con, không phụ thuộc vào tên cụ thể của các màu.

Hình 1: Một cách tô màu có độ rực rỡ \([3,2,1,2,1,1]\); các đỉnh \(0,1,5\) cùng màu, các đỉnh \(2,4\) cùng màu và đỉnh \(3\) mang màu còn lại.

Một quy luật được mô tả bằng tập \(S\subseteq\{1,2,\ldots,n-1\}\). Một cách tô màu thỏa quy luật \(S\) khi với mọi \(u\in S\), tồn tại một tổ tiên thực sự \(p\) của \(u\) có cùng màu với \(u\).

Gọi \(w_S\) là số dãy độ rực rỡ khác nhau có thể thu được từ những cách tô màu thỏa quy luật \(S\). Hai độ rực rỡ khác nhau khi ít nhất một vị trí trong hai dãy khác nhau.

Hãy tính

theo modulo \(998\,244\,353\).

Yêu cầu cài đặt

Bạn không được cài đặt hàm main. Submission phải include rainbow.h và cài đặt:

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

• c là số hiệu test; c=0 biểu thị dữ liệu mẫu.
• n là số đỉnh.
• f có độ dài \(n\), với \(f_0=0\) và \(f_i\) là cha của \(i\) khi \(1\le i<n\).
• Hàm phải trả về tổng cần tìm theo modulo \(998\,244\,353\).
• Bộ chấm gọi hàm đúng một lần cho mỗi test.

Khung khai báo:

#include "rainbow.h"

Dữ liệu bộ chấm

• Dòng đầu chứa \(c,n\).
• Dòng thứ hai chứa \(f_1,f_2,\ldots,f_{n-1}\).

Grader ghi một số nguyên là giá trị trả về của rainbow.

Ràng buộc

• \(1\le n\le200\).
• \(0\le f_i<i\) với mọi \(1\le i<n\).

Phân nhóm

Mỗi test có giá trị \(4\) điểm.

• Tính chất A: \(f_i=i-1\) với mọi \(1\le i<n\); cây là một đường đi.
• Tính chất B: với mọi đỉnh \(i\), có không quá hai đỉnh \(j\) thỏa \(f_j=i\).

Ví dụ

0 3
0 0

8

0 6
0 1 0 3 1

279

Nguồn

CCF NOI 2026 - Ngày 2, bài Rainbow Tree. Đề và dữ liệu chính thức được phát hành theo giấy phép CC BY-NC.