Universal Cup Judging System

Universal Cup

Limite de temps : 8.0 s Limite de mémoire : 256 MB Points totaux : 100 Hackable ✓
Statistiques

Aleksei sai syntymäpäivälahjaksi omenapuun, jonka koko on $n$. Kilpaohjelmoijana hän päätti laskea puussa olevien $k$-omenapiirakoiden lukumäärän.

Kokoa $n$ oleva omenapuu määritellään $n$-solmuiseksi juurelliseksi puuksi, jonka juuri on solmu $1$ ja jossa jokaisella solmulla on aidosti vähemmän suoria lapsia kuin sen vanhemmalla (lukuun ottamatta juurta, jolla ei ole vanhempaa).

$k$-omenapiirakka on pari $(v, S)$, missä:

  • $v \in V$ on puun solmu (keskus),
  • $S \subset V \setminus \{v\}$ on solmujen joukko, jonka koko on $k - 1$,
  • on olemassa sellainen kokonaisluku $d$, että kaikilla $u \in S$ pätee $\text{dist}(v, u) = d$.

Etäisyys $\text{dist}(u, v)$ määritellään solmujen $u$ ja $v$ välisen yksinkertaisen polun kaarien lukumääräksi.

Toisin sanoen $k$-omenapiirakka koostuu yhdestä solmusta $v$ (keskuksesta) sekä $k - 1$ muusta solmusta, jotka ovat kaikki samalla etäisyydellä solmusta $v$.

Tehtäväsi on laskea $k$-omenapiirakoiden lukumäärä annetussa puussa.

Koska vastaus voi olla suuri, tulosta se modulo $998\,244\,353$.

Syöte

Jokainen testi sisältää useita testitapauksia. Ensimmäinen rivi sisältää testitapausten lukumäärän $t$ ($1 \le t \le 10^4$). Seuraavaksi annetaan testitapausten kuvaukset.

Jokainen testitapaus alkaa rivillä, joka sisältää kaksi kokonaislukua $n$ ja $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$): omenapuun solmujen lukumäärän ja omenapiirakan koon.

Seuraava rivi sisältää $n - 1$ kokonaislukua $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), missä $p_i$ tarkoittaa solmun $i$ vanhempaa omenapuussa.

Lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $5 \cdot 10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi kokonaisluku: $k$-omenapiirakoiden lukumäärä modulo $998\,244\,353$.

Esimerkit

Syöte 1

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

Tuloste 1

1
20
16

Huomautus

Ensimmäisessä testitapauksessa ainoa olemassa oleva piirakka on keskittynyt solmuun $1$, ja sitä vastaava joukko on $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.