Universal Cup Judging System

Universal Cup

実行時間制限: 8.0 s メモリ制限: 256 MB 満点: 100 ハック可能 ✓
統計

Aleksei nhận được một cây táo kích thước $n$ làm quà sinh nhật. Là một lập trình viên thi đấu, anh ấy quyết định tính số lượng bánh táo cỡ $k$ ($k$-apple pies) trên cây.

Một cây táo kích thước $n$ được định nghĩa là một cây có gốc gồm $n$ đỉnh, gốc tại đỉnh $1$, trong đó mỗi đỉnh có số con trực tiếp ít hơn hẳn so với cha của nó (ngoại trừ đỉnh gốc không có cha).

Một bánh táo cỡ $k$ là một cặp $(v, S)$ trong đó:

  • $v \in V$ là một đỉnh của cây (tâm),
  • $S \subset V \setminus \{v\}$ là một tập hợp các đỉnh có kích thước $k - 1$,
  • tồn tại một số nguyên $d$ sao cho với mọi $u \in S$, $\text{dist}(v, u) = d$.

Khoảng cách $\text{dist}(u, v)$ được định nghĩa là số cạnh trên đường đi đơn giữa hai đỉnh $u$ và $v$.

Nói cách khác, một bánh táo cỡ $k$ bao gồm một đỉnh $v$ (tâm) và $k - 1$ đỉnh khác đều có cùng khoảng cách đến $v$.

Nhiệm vụ của bạn là tính số lượng bánh táo cỡ $k$ trong cây đã cho.

Vì đáp án có thể rất lớn, hãy in ra kết quả theo modulo $998\,244\,353$.

Dữ liệu vào

Mỗi test chứa nhiều bộ dữ liệu. Dòng đầu tiên chứa số lượng bộ dữ liệu $t$ ($1 \le t \le 10^4$). Mô tả của các bộ dữ liệu theo sau.

Mỗi bộ dữ liệu bắt đầu bằng một dòng chứa hai số nguyên $n$ và $k$ ($2 \le n \le 5 \cdot 10^5$, $1 \le k \le n$): số đỉnh trong cây táo và kích thước của bánh táo.

Dòng tiếp theo chứa $n - 1$ số nguyên $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), trong đó $p_i$ biểu thị cha của đỉnh $i$ trong cây táo.

Tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $5 \cdot 10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất: số lượng bánh táo cỡ $k$ theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1
20
16

Ghi chú

Trong bộ dữ liệu đầu tiên, chiếc bánh duy nhất tồn tại có tâm tại đỉnh $1$, và tập hợp tương ứng là $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.