Universal Cup Judging System

Universal Cup

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

Aleksei otrzymał w prezencie urodzinowym jabłoń o rozmiarze $n$. Jako programista startujący w zawodach postanowił obliczyć liczbę $k$-jabłeczników na tym drzewie.

Jabłoń o rozmiarze $n$ definiujemy jako drzewo ukorzenione o $n$ wierzchołkach, z korzeniem w wierzchołku $1$, w którym każdy wierzchołek ma ściśle mniej bezpośrednich synów niż jego ojciec (z wyjątkiem korzenia, który nie ma ojca).

$k$-jabłecznik to para $(v, S)$, gdzie:

  • $v \in V$ jest wierzchołkiem drzewa (środkiem),
  • $S \subset V \setminus \{v\}$ jest zbiorem wierzchołków o rozmiarze $k - 1$,
  • istnieje taka liczba całkowita $d$, że dla każdego $u \in S$ zachodzi $\text{dist}(v, u) = d$.

Odległość $\text{dist}(u, v)$ jest zdefiniowana jako liczba krawędzi na ścieżce prostej między wierzchołkami $u$ i $v$.

Innymi słowy, $k$-jabłecznik składa się z jednego wierzchołka $v$ (środka) oraz $k - 1$ innych wierzchołków, które znajdują się w tej samej odległości od $v$.

Twoim zadaniem jest obliczenie liczby $k$-jabłeczników w danym drzewie.

Ponieważ odpowiedź może być duża, wypisz ją modulo $998\,244\,353$.

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwszy wiersz zawiera liczbę przypadków testowych $t$ ($1 \le t \le 10^4$). Następnie podane są opisy kolejnych przypadków testowych.

Każdy przypadek testowy zaczyna się od wiersza zawierającego dwie liczby całkowite $n$ oraz $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$): liczbę wierzchołków jabłoni oraz rozmiar jabłecznika.

Kolejny wiersz zawiera $n - 1$ liczb całkowitych $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), gdzie $p_i$ oznacza ojca wierzchołka $i$ w jabłoni.

Suma wartości $n$ po wszystkich przypadkach testowych nie przekracza $5 \cdot 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jedną liczbę całkowitą: liczbę $k$-jabłeczników modulo $998\,244\,353$.

Przykład

Wejście 1

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

Wyjście 1

1
20
16

Uwagi

W pierwszym przypadku testowym jedyny istniejący jabłecznik ma środek w wierzchołku $1$, a odpowiadający mu zbiór to $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.