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.