Universal Cup Judging System

Universal Cup

时间限制: 8.0 s 内存限制: 256 MB 总分: 100 可 Hack ✓
统计

Aleksei 收到了一棵大小為 $n$ 的蘋果樹作為生日禮物。身為一名程式競賽選手,他決定計算樹上 $k$-蘋果派的數量。

一棵大小為 $n$ 的蘋果樹定義為一棵有 $n$ 個頂點、以頂點 $1$ 為根的有根樹,其中每個頂點的直接子節點數量都嚴格少於其父節點的直接子節點數量(沒有父節點的根節點除外)。

一個 $k$-蘋果派是一個二元組 $(v, S)$,其中:

  • $v \in V$ 是樹的一個頂點(稱為中心),
  • $S \subset V \setminus \{v\}$ 是一個大小為 $k - 1$ 的頂點集合,
  • 存在一個整數 $d$,使得對於每個 $u \in S$,都有 $\text{dist}(v, u) = d$。

距離 $\text{dist}(u, v)$ 定義為頂點 $u$ 與 $v$ 之間簡單路徑上的邊數。

換句話說,一個 $k$-蘋果派由一個頂點 $v$(中心)以及另外 $k - 1$ 個與 $v$ 距離相同的頂點組成。

你的任務是計算給定的樹中 $k$-蘋果派的數量。

由於答案可能很大,請將其對 $998\,244\,353$ 取模後輸出。

輸入格式

每個測試包含多組測試資料。第一行包含測試資料的組數 $t$($1 \le t \le 10^4$)。接下來是各組測試資料的描述。

每組測試資料的第一行包含兩個整數 $n$ 與 $k$($2 \le n \le 5 \cdot 10^5$,$1 \le k \le n$):分別代表蘋果樹的頂點數與蘋果派的大小。

下一行包含 $n - 1$ 個整數 $p_2, p_3, \dots, p_n$($1 \le p_i < i$),其中 $p_i$ 代表蘋果樹中頂點 $i$ 的父節點。

所有測試資料中 $n$ 的總和不超過 $5 \cdot 10^5$。

輸出格式

對於每組測試資料,輸出一個整數:$k$-蘋果派的數量對 $998\,244\,353$ 取模後的結果。

範例

輸入格式 1

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

輸出格式 1

1
20
16

說明

在第一組測試資料中,唯一存在的派以頂點 $1$ 為中心,對應的集合為 $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.