Universal Cup Judging System

Universal Cup

実行時間制限: 8.0 s メモリ制限: 256 MB 満点: 100 ハック可能 ✓
統計

Алексей туған күніне сыйлық ретінде өлшемі $n$ болатын алма ағашын алды. Спорттық бағдарламашы ретінде ол ағаштағы $k$-алма бәліштерінің санын есептеуді ұйғарды.

Өлшемі $n$ болатын алма ағашы деп төбесі $1$-де орналасқан, $n$ төбеден тұратын түбірлі ағаш аталады, мұнда әрбір төбенің тікелей ұрпақтарының саны оның ата-анасының тікелей ұрпақтарының санынан қатаң түрде аз (ата-анасы жоқ түбірден басқа).

$k$-алма бәліші — бұл $(v, S)$ жұбы, мұндағы:

  • $v \in V$ — ағаштың төбесі (орталығы),
  • $S \subset V \setminus \{v\}$ — өлшемі $k - 1$ болатын төбелер жиыны,
  • әрбір $u \in S$ үшін $\text{dist}(v, u) = d$ орындалатындай бүтін $d$ саны табылады.

$\text{dist}(u, v)$ арақашықтығы $u$ мен $v$ төбелерінің арасындағы қарапайым жолдағы қырлар саны ретінде анықталады.

Басқаша айтқанда, $k$-алма бәліші бір $v$ төбесінен (орталықтан) және $v$ төбесінен бірдей қашықтықта орналасқан басқа $k - 1$ төбеден тұрады.

Сіздің міндетіңіз — берілген ағаштағы $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$-нен аспайды.

Шығыс деректері

Әрбір тест жиынтығы үшін бір бүтін санды шығарыңыз: $998\,244\,353$ модулі бойынша $k$-алма бәліштерінің саны.

Мысалдар

Кіріс деректері 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.