Universal Cup Judging System

Universal Cup

Límite de tiempo: 8.0 s Límite de memoria: 256 MB Puntuación total: 100 Hackeable ✓
Estadísticas

Aleksei a reçu un pommier de taille $n$ comme cadeau d'anniversaire. Étant lui-même adepte de programmation compétitive, il a décidé de calculer le nombre de tartes à $k$ pommes dans l'arbre.

Un pommier de taille $n$ est défini comme un arbre enraciné à $n$ sommets, dont la racine est le sommet $1$, où chaque sommet possède strictement moins d'enfants directs que son parent (à l'exception de la racine qui n'a pas de parent).

Une tarte à $k$ pommes est un couple $(v, S)$ où :

  • $v \in V$ est un sommet de l'arbre (le centre),
  • $S \subset V \setminus \{v\}$ est un ensemble de sommets de taille $k - 1$,
  • il existe un entier $d$ tel que pour tout $u \in S$, $\text{dist}(v, u) = d$.

La distance $\text{dist}(u, v)$ est définie comme le nombre d'arêtes sur le chemin simple reliant les sommets $u$ et $v$.

Autrement dit, une tarte à $k$ pommes est constituée d'un sommet $v$ (le centre) et de $k - 1$ autres sommets situés tous à la même distance de $v$.

Votre tâche consiste à calculer le nombre de tartes à $k$ pommes dans l'arbre donné.

Comme la réponse peut être grande, affichez-la modulo $998\,244\,353$.

Entrée

Chaque test contient plusieurs cas de test. La première ligne contient le nombre de cas de test $t$ ($1 \le t \le 10^4$). La description des cas de test suit.

Chaque cas de test commence par une ligne contenant deux entiers $n$ et $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$) : le nombre de sommets dans le pommier et la taille de la tarte aux pommes.

La ligne suivante contient $n - 1$ entiers $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), où $p_i$ désigne le parent du sommet $i$ dans le pommier.

La somme de $n$ sur l'ensemble des cas de test ne dépasse pas $5 \cdot 10^5$.

Sortie

Pour chaque cas de test, affichez un seul entier : le nombre de tartes à $k$ pommes modulo $998\,244\,353$.

Exemples

Entrée 1

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

Sortie 1

1
20
16

Remarque

Dans le premier cas de test, la seule tarte existante est centrée sur le sommet $1$, et l'ensemble correspondant est $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.