Universal Cup Judging System

Universal Cup

時間限制: 8.0 s 記憶體限制: 256 MB 總分: 100 可 Hack ✓
统计

تلقى أليكسي شجرة تفاح بحجم $n$ كهدية لعيد ميلاده. وبصفته مبرمجًا تنافسيًا، قرر حساب عدد فطائر التفاح من الحجم $k$ على الشجرة.

تُعرَّف شجرة التفاح ذات الحجم $n$ بأنها شجرة مجذرة تتكون من $n$ رأسًا، جذرها عند الرأس $1$، حيث يمتلك كل رأس عددًا من الأبناء المباشرين أقل تمامًا من عدد الأبناء المباشرين لأبيه (باستثناء الجذر الذي ليس له أب).

فطيرة التفاح من الحجم $k$ هي زوج $(v, S)$ حيث:

  • $v \in V$ هو رأس في الشجرة (المركز)،
  • $S \subset V \setminus \{v\}$ هي مجموعة من الرؤوس حجمها $k - 1$،
  • يوجد عدد صحيح $d$ بحيث إنه لكل $u \in S$، يكون $\text{dist}(v, u) = d$.

تُعرَّف المسافة $\text{dist}(u, v)$ بأنها عدد الحواف في المسار البسيط بين الرأسين $u$ و $v$.

بعبارة أخرى، تتكون فطيرة التفاح من الحجم $k$ من رأس واحد $v$ (المركز) و $k - 1$ من الرؤوس الأخرى التي تقع جميعها على نفس المسافة من $v$.

مهمتك هي حساب عدد فطائر التفاح من الحجم $k$ في الشجرة المعطاة.

بما أن الإجابة قد تكون كبيرة، اطبعها باقي قسمتها على $998\,244\,353$.

الإدخال

يحتوي كل اختبار على عدة حالات اختبار. يحتوي السطر الأول على عدد حالات الاختبار $t$ ($1 \le t \le 10^4$). يلي ذلك وصف حالات الاختبار.

تبدأ كل حالة اختبار بسطر يحتوي على عددين صحيحين $n$ و $k$ ($2 \le n \le 5 \cdot 10^5$، $1 \le k \le n$): عدد الرؤوس في شجرة التفاح وحجم فطيرة التفاح.

يحتوي السطر التالي على $n - 1$ من الأعداد الصحيحة $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$)، حيث يمثل $p_i$ أب الرأس $i$ في شجرة التفاح.

مجموع $n$ عبر جميع حالات الاختبار لا يتجاوز $5 \cdot 10^5$.

الإخراج

لكل حالة اختبار، اطبع عددًا صحيحًا واحدًا: عدد فطائر التفاح من الحجم $k$ باقي قسمته على $998\,244\,353$.

أمثلة

الإدخال 1

3
3 3
1 1
5 2
1 1 2 3
6 3
1 1 1 2 2

الإخراج 1

1
20
16

ملاحظة

في حالة الاختبار الأولى، الفطيرة الوحيدة الموجودة مركزها عند الرأس $1$، والمجموعة المقابلة هي $S = \{2, 3\}$.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#2360EditorialOpenNew Editorial for Problem #14130cqbzzlrView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.