Universal Cup Judging System

Universal Cup

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

Aleksei ได้รับต้นแอปเปิลขนาด $n$ เป็นของขวัญวันเกิด ในฐานะนักเขียนโปรแกรมเชิงแข่งขัน เขาจึงตัดสินใจคำนวณจำนวนพายแอปเปิลขนาด $k$ ($k$-apple pies) บนต้นไม้นี้

ต้นแอปเปิลขนาด $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.