Universal Cup Judging System

Universal Cup

시간 제한: 8.0 s 메모리 제한: 256 MB 총점: 100 해킹 가능 ✓
통계

אלכסיי קיבל עץ תפוחים בגודל $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.