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.