Universal Cup Judging System

Universal Cup

時間限制: 8.0 s 記憶體限制: 256 MB 總分: 100 可 Hack ✓
统计

Aleksei recibió un manzano de tamaño $n$ como regalo de cumpleaños. Como programador competitivo que es, decidió calcular el número de tartas de $k$ manzanas en el árbol.

Un manzano de tamaño $n$ se define como un árbol con raíz de $n$ vértices, con raíz en el vértice $1$, donde cada vértice tiene estrictamente menos hijos directos que su padre (excepto la raíz, que no tiene padre).

Una tarta de $k$ manzanas es un par $(v, S)$ donde:

  • $v \in V$ es un vértice del árbol (el centro),
  • $S \subset V \setminus \{v\}$ es un conjunto de vértices de tamaño $k - 1$,
  • existe un entero $d$ tal que para todo $u \in S$, $\text{dist}(v, u) = d$.

La distancia $\text{dist}(u, v)$ se define como el número de aristas en el camino simple entre los vértices $u$ y $v$.

En otras palabras, una tarta de $k$ manzanas consta de un vértice $v$ (el centro) y otros $k - 1$ vértices que se encuentran todos a la misma distancia de $v$.

Tu tarea es calcular el número de tartas de $k$ manzanas en el árbol dado.

Como la respuesta puede ser muy grande, imprímela módulo $998\,244\,353$.

Entrada

Cada prueba contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba $t$ ($1 \le t \le 10^4$). A continuación sigue la descripción de los casos de prueba.

Cada caso de prueba comienza con una línea que contiene dos enteros $n$ y $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$): el número de vértices en el manzano y el tamaño de la tarta de manzanas.

La siguiente línea contiene $n - 1$ enteros $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), donde $p_i$ denota el padre del vértice $i$ en el manzano.

La suma de $n$ en todos los casos de prueba no supera $5 \cdot 10^5$.

Salida

Para cada caso de prueba, imprime un único entero: el número de tartas de $k$ manzanas módulo $998\,244\,353$.

Ejemplos

Entrada 1

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

Salida 1

1
20
16

Nota

En el primer caso de prueba, la única tarta existente tiene su centro en el vértice $1$, y el conjunto correspondiente es $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.