Universal Cup Judging System

Universal Cup

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

Aleksei menerima sebuah pohon apel berukuran $n$ sebagai hadiah ulang tahun. Sebagai seorang pemrogram kompetitif, ia memutuskan untuk menghitung banyaknya pai apel-$k$ ($k$-apple pies) pada pohon tersebut.

Sebuah pohon apel berukuran $n$ didefinisikan sebagai pohon berakar dengan $n$ simpul, berakar di simpul $1$, di mana setiap simpul memiliki anak langsung yang lebih sedikit secara ketat daripada induknya (kecuali akar yang tidak memiliki induk).

Sebuah pai apel-$k$ adalah pasangan $(v, S)$ di mana:

  • $v \in V$ adalah sebuah simpul dari pohon (pusat),
  • $S \subset V \setminus \{v\}$ adalah himpunan simpul berukuran $k - 1$,
  • terdapat sebuah bilangan bulat $d$ sedemikian sehingga untuk setiap $u \in S$, berlaku $\text{dist}(v, u) = d$.

Jarak $\text{dist}(u, v)$ didefinisikan sebagai banyaknya sisi pada lintasan sederhana antara simpul $u$ dan $v$.

Dengan kata lain, sebuah pai apel-$k$ terdiri atas satu simpul $v$ (pusat) dan $k - 1$ simpul lainnya yang semuanya berada pada jarak yang sama dari $v$.

Tugas Anda adalah menghitung banyaknya pai apel-$k$ pada pohon yang diberikan.

Karena jawabannya bisa sangat besar, keluarkan hasilnya modulo $998\,244\,353$.

Masukan

Setiap pengujian berisi beberapa kasus uji. Baris pertama berisi banyaknya kasus uji $t$ ($1 \le t \le 10^4$). Deskripsi dari masing-masing kasus uji menyusul.

Setiap kasus uji dimulai dengan satu baris yang berisi dua bilangan bulat $n$ dan $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$): banyaknya simpul pada pohon apel dan ukuran pai apel.

Baris berikutnya berisi $n - 1$ bilangan bulat $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), di mana $p_i$ menyatakan induk dari simpul $i$ pada pohon apel.

Jumlah $n$ di seluruh kasus uji tidak melebihi $5 \cdot 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan satu bilangan bulat: banyaknya pai apel-$k$ modulo $998\,244\,353$.

Contoh

Masukan 1

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

Keluaran 1

1
20
16

Catatan

Pada kasus uji pertama, satu-satunya pai yang ada berpusat di simpul $1$, dan himpunan yang bersesuaian adalah $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.