تقول الأسطورة إن في دولة الليل شجرة قوس قزح تضم $n$ عقدة. وهي شجرة مجذّرة، عقدها مرقّمة من $0$ إلى $n-1$، والعقدة $0$ هي جذرها. وأب العقدة $i$، حيث $1\leq i<n$، هو $f_i$.

يمكن لكل عقدة في شجرة قوس قزح أن تظهر بأي لون. توجد ألوان لا نهائية، لكن التنوّع اللوني للشجرة لا يعتمد إلا على عدد الألوان المختلفة الظاهرة في كل شجرة فرعية، ولا يعتمد على ماهية الألوان نفسها. وبالتحديد، إذا وُجدت $c_i$ ألوان مختلفة بين عقد الشجرة الفرعية المجذّرة عند العقدة $i$، حيث $0\leq i<n$، فيمكن تمثيل تنوّع الشجرة اللوني بالتسلسل $[c_0,c_1,\ldots,c_{n-1}]$. في الشكل التالي مثلاً، العقد $0,1,5$ زرقاء، والعقدتان $2,4$ حمراوان، والعقدة $3$ صفراء؛ لذا يكون التنوّع اللوني $[3,2,1,2,1,1]$.

تؤدي تغيّرات السحب إلى ظهور ألوان الشجرة وفق نمط معين. وبالتحديد، يمكن وصف كل نمط بمجموعة جزئية مقابلة من العقد $S\subseteq\{1,2,\ldots,n-1\}$: تشترك كل عقدة $u$ في $S$ في لونها مع أحد أسلافها. وبصياغة رسمية، لكل $u\in S$، يوجد سلف $p$ للعقدة $u$، حيث $p\neq u$، له اللون نفسه. ورغم التقيد بهذا النمط، تستطيع الشجرة إظهار ألوان مختلفة وتكوين تنوّعات لونية مختلفة. نرمز إلى عدد الأنواع من التنوّع اللوني الممكنة لشجرة قوس قزح التي تحقق النمط $S$ بـ $w_S$. ويختلف تنوّعان لونيان إذا وفقط إذا اختلف عنصر واحد على الأقل في تسلسليهما.

احسب مجموع أعداد أنواع التنوّع اللوني للشجرة التي تحقق كل نمط، عبر جميع الأنماط الممكنة وعددها $2^{n-1}$، أي $\sum_{S\subseteq\{1,2,\ldots,n-1\}}w_S$. ولأن الإجابة قد تكون كبيرة، يكفي حسابها بترديد $998\,244\,353$.

تفاصيل التنفيذ

لا يحتاج المتسابق إلى تنفيذ الدالة main، ولا ينبغي له تنفيذها.

يجب التأكد من أن ملف المصدر المقدّم يتضمن الترويسة rainbow.h، وذلك بإضافة الشيفرة التالية في بداية البرنامج:

#include "rainbow.h"

عليك تنفيذ الدالة التالية في ملف المصدر المقدّم rainbow.cpp:

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

• يمثّل $c,n$ رقم حالة الاختبار وعدد عقد شجرة قوس قزح على الترتيب. وتعني $c=0$ أن حالة الاختبار مثال.

• $f$ تسلسل طوله $n$، حيث $f_0=0$، ويمثّل $f_i$، حيث $1\leq i<n$، أب العقدة $i$.

• يجب أن تعيد الدالة مجموع أعداد أنواع التنوّع اللوني لشجرة قوس قزح التي تحقق كل نمط، بترديد $998\,244\,353$.

• لكل حالة اختبار، يستدعي برنامج التقييم هذه الدالة مرة واحدة بالضبط.

الملف template_rainbow.cpp في مجلد المسألة هو الشيفرة النموذجية المقدّمة، ويمكنك الاسترشاد به لكتابة تنفيذك.

كيفية اختبار البرنامج

يمكنك استخدام الأمر التالي في مجلد المسألة لترجمة البرنامج والحصول على ملف تنفيذي:

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

0 3
0 0

الإخراج 1

8

ملاحظة

• توجد ثلاثة تنوّعات لونية لشجرة قوس قزح تحقق النمط $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$.

الإدخال 2

0 6
0 1 0 3 1

الإخراج 2

279

أمثلة 3

انظر الملفين rainbow/rainbow3.in وrainbow/rainbow3.ans في مجلد المتسابق.

يحقق هذا المثال قيود حالتي الاختبار $3,4$.

أمثلة 4

انظر الملفين rainbow/rainbow4.in وrainbow/rainbow4.ans في مجلد المتسابق.

يحقق هذا المثال قيود حالات الاختبار من $5$ إلى $7$.

أمثلة 5

انظر الملفين rainbow/rainbow5.in وrainbow/rainbow5.ans في مجلد المتسابق.

يحقق هذا المثال قيود حالتي الاختبار $8,9$.

أمثلة 6

انظر الملفين rainbow/rainbow6.in وrainbow/rainbow6.ans في مجلد المتسابق.

يحقق هذا المثال قيود حالات الاختبار من $10$ إلى $12$.

القيود

لجميع بيانات الاختبار:

• $1\leq n\leq200$؛

• لكل $1\leq i<n$، لدينا $0\leq f_i<i$.

الخاصية الخاصة A: لكل $1\leq i<n$، لدينا $f_i=i-1$.

الخاصية الخاصة B: لكل $0\leq i<n$، يوجد على الأكثر فهرسان $j$ يحققان $f_j=i$.