久莲 فتاة تحب تأليف المسائل.
بعد انتهاء World Final هذا العام، أصبحت 久莲 مولعة بالهندسة الحسابية، فقرّرت تقديم مسألة هندسة حسابية في امتحان NOI أيضاً: إنها مسألة لا يرتبط بالهندسة الحسابية فيها إلا اسمها.
أولاً، تعطي 久莲 شجرة مجذّرة $T$ ذات $n$ عقد، حيث $n\geq2$، ورقم الجذر هو $1$. نعرّف الأوراق بأنها جميع العقد غير الجذر التي درجتها $1$ بالضبط. الشكل التالي مثال لشجرة $T$، ومجموعة أوراقها هي $\{3,4,5\}$.
بعد ذلك، تبني 久莲 تسلسلاً $A$ باستخدام الشجرة:
تُجرى زيارة بالعمق أولاً للشجرة كلها بدءاً من الجذر، مع زيارة الأبناء بترتيب أرقامهم تصاعدياً. وهكذا نحصل على ترتيب DFS للشجرة $T$.
ثم ترتّب 久莲 جميع الأوراق وفق ترتيب ظهورها من البداية إلى النهاية في ترتيب DFS، لتحصل على التسلسل $A$.
وبالاعتماد على $A$، تعرّف 久莲 المسافة $d(u,v)$ بين ورقتين $u,v$ كما يلي: إذا كانت $u$ العنصر $i$ في $A$، وكانت $v$ العنصر $j$، فإن $d(u,v)=\min(|i-j|,|A|-|i-j|)$. هنا $|A|$ هو طول التسلسل، أي عدد أوراق $T$، و$i,j$ هما موضعا الظهور، ويبدأ العد من $1$.
في المثال السابق، $A=[4,5,3]$، ولدينا $d(3,5)=d(3,4)=d(4,5)=1$، ومواضع ظهور $3,4,5$ هي $3,1,2$ على الترتيب.
أخيراً، تعطي 久莲 معاملاً $K$. باستخدام الشجرة المجذّرة $T$ والتسلسل $A$، يمكننا بناء رسم بياني غير موجّه $G$ ذي $n$ عقد، بلا حواف مكرّرة ولا حلقات ذاتية. توجد حافة بين عقدتين مختلفتين $u,v$ إذا وفقط إذا تحقق واحد على الأقل من الشرطين التاليين:
توجد في الشجرة $T$ حافة تربط $u,v$.
كل من $u,v$ ورقة في الشجرة $T$، و$d(u,v)\leq K$.
عندما $K=1$ أو $K=2$، يكون الرسم البياني $G$ الناتج عن المثال السابق كما في الشكل التالي في الحالتين.
تريد 久莲 منك الآن حساب عدد الدورات الهاملتونية المختلفة في $G$. قد تكون الإجابة كبيرة جداً، فأخرجها بترديد $998244353$.
فيما يلي بعض التعريفات الإضافية:
الدورة الهاملتونية $H$ في رسم بياني غير موجّه $G$ بلا حواف مكرّرة ولا حلقات ذاتية هي مجموعة جزئية من حواف $G$، بحيث تنتمي إلى $H$ بالضبط حافتان مختلفتان مجاورتان لكل عقدة، ويمكن الوصول بين أي عقدتين مباشرة أو بصورة غير مباشرة باستخدام حواف $H$.
تختلف دورتان هاملتونيتان $H_1,H_2$ في رسم بياني غير موجّه $G$ بلا حواف مكرّرة ولا حلقات ذاتية إذا وفقط إذا وُجدت حافة $e$ تنتمي إلى $H_1$ ولا تنتمي إلى $H_2$.
الإدخال
تُقرأ البيانات من الملف polygon.in.
يحتوي السطر الأول على عددين صحيحين $n,K$، يمثّلان عدد عقد الشجرة $T$ والمعامل $K$ الذي اختارته 久莲.
يحتوي السطر الثاني على $n-1$ عدداً صحيحاً $f_i$، حيث $1\leq f_i\leq i$، ويعني $f_i$ وجود الحافة $(f_i,i+1)$ في الشجرة $T$.
الإخراج
تُكتب النتائج في الملف polygon.out.
أخرج في سطر واحد عدداً صحيحاً واحداً، يمثّل عدد الدورات الهاملتونية بترديد $998244353$.
أمثلة
الإدخال 1
5 1 1 1 2 2
الإخراج 1
2
ملاحظة
يطابق هذا المثال المثال الوارد في وصف المسألة تماماً. وترتيبا العقد على الدورتين الهاملتونيتين هما $(1,2,4,5,3)$ و$(1,2,5,4,3)$.
المهام الفرعية
أحجام بيانات حالات الاختبار وخصائصها موضّحة في الجدول التالي:
| الرقم | $n$ | $K$ | الخاصية الخاصة | الرقم | $n$ | $K$ | الخاصية الخاصة |
|---|---|---|---|---|---|---|---|
| $1$ | $\leq5$ | $\leq3$ | لا توجد | $11$ | $\leq1000$ | $\leq2$ | A |
| $2$ | $\leq10$ | $\leq3$ | لا توجد | $12$ | $\leq1000$ | $\leq2$ | A |
| $3$ | $\leq15$ | $\leq3$ | لا توجد | $13$ | $\leq1000$ | $\leq2$ | A |
| $4$ | $\leq20$ | $\leq3$ | لا توجد | $14$ | $\leq1000$ | $\leq2$ | لا توجد |
| $5$ | $\leq1000$ | $=1$ | A | $15$ | $\leq1000$ | $\leq2$ | لا توجد |
| $6$ | $\leq1000$ | $=1$ | A | $16$ | $\leq1000$ | $\leq2$ | لا توجد |
| $7$ | $\leq1000$ | $=1$ | A | $17$ | $\leq1000$ | $\leq3$ | A |
| $8$ | $\leq1000$ | $=1$ | لا توجد | $18$ | $\leq1000$ | $\leq3$ | A |
| $9$ | $\leq1000$ | $=1$ | لا توجد | $19$ | $\leq1000$ | $\leq3$ | لا توجد |
| $10$ | $\leq1000$ | $=1$ | لا توجد | $20$ | $\leq1000$ | $\leq3$ | لا توجد |
الخاصية A تعني أننا نضمن أن لكل عقدة في الشجرة ابنين على الأكثر.
لجميع البيانات، نضمن أن $1\leq f_i\leq i$، و$2\leq n\leq1000$.