Universal Cup Judging System

Universal Cup

حد الوقت: 8.0 s حد الذاكرة: 256 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

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.