Universal Cup Judging System

Universal Cup

Süre Sınırı: 8.0 s Bellek Sınırı: 256 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Aleksei fékk eplatré af stærð $n$ í afmælisgjöf. Sem keppnisforritari ákvað hann að reikna fjölda $k$-eplabaka á trénu.

Eplatré af stærð $n$ er skilgreint sem rótað tré með $n$ hnútum, með rót í hnúti $1$, þar sem hver hnútur á strangt færri bein börn en foreldri sitt (nema rótin sem á ekkert foreldri).

$k$-eplabaka er par $(v, S)$ þar sem:

  • $v \in V$ er hnútur í trénu (miðjan),
  • $S \subset V \setminus \{v\}$ er mengi hnúta af stærð $k - 1$,
  • til er heiltala $d$ þannig að fyrir sérhvert $u \in S$ gildir $\text{dist}(v, u) = d$.

Fjarlægðin $\text{dist}(u, v)$ er skilgreind sem fjöldi leggja á einfalda veginum milli hnútanna $u$ og $v$.

Með öðrum orðum samanstendur $k$-eplabaka af einum hnúti $v$ (miðjunni) og $k - 1$ öðrum hnútum sem eru allir í sömu fjarlægð frá $v$.

Verkefni þitt er að reikna fjölda $k$-eplabaka í gefna trénu.

Þar sem svarið getur verið stórt skal prenta það modulo $998\,244\,353$.

Inntak

Hvert próf inniheldur mörg prófunartilfelli. Fyrsta línan inniheldur fjölda prófunartilfella $t$ ($1 \le t \le 10^4$). Lýsing á prófunartilfellunum fylgir.

Hvert prófunartilfelli byrjar á línu sem inniheldur tvær heiltölur $n$ og $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$): fjölda hnúta í eplatrénu og stærð eplabökunnar.

Næsta lína inniheldur $n - 1$ heiltölur $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), þar sem $p_i$ táknar foreldri hnúts $i$ í eplatrénu.

Summa $n$ yfir öll prófunartilfelli fer ekki yfir $5 \cdot 10^5$.

Úttak

Fyrir hvert prófunartilfelli skal prenta eina heiltölu: fjölda $k$-eplabaka modulo $998\,244\,353$.

Dæmi

Inntak 1

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

Úttak 1

1
20
16

Skýring

Í fyrsta prófunartilfellinu hefur eina bakan sem er til miðju í hnúti $1$, og samsvarandi mengi er $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.