← 返回题目列表

Codeforces · 2182/G

G. 短花环

中文机器翻译题面 查看原题

Monocarp 想在圣诞树上挂一个花环。

圣诞树是一棵具有 $$$n$$$ 个顶点的树,根部为顶点 $$$1$$$。树的两个顶点之间的距离是它们之间的最短路径上的边的数量,顶点的深度是从它到根的距离。

花环由通过电线连接的 $$$n$$$ 灯泡组成,编号从 $$$1$$$ 到 $$$n$$$。每两个相邻灯泡之间的电线长度为$$$k$$$。

花环必须按照以下规则挂在树上:

  • 每个球茎必须放置在树的一个顶点上,并且每个顶点上必须恰好有一个球茎;
  • 灯泡 $$$1$$$ 必须放置在树根上;
  • 每个后续灯泡都必须放置在其父顶点上有灯泡的顶点上。如果有多个这样的顶点,则选择深度最大的顶点。如果还有多个选项,可以选择任意一个;
  • 对于每对后续灯泡,它们放置的顶点之间的距离不得超过 $$$k$$$。

你的任务是计算在遵守所有规则的情况下悬挂花环的方法的数量,并以 $$$998244353$$$ 为模输出。如果 [1, n]$$$ 中至少存在一个整数 $$$i \ 使得第 $$$i$$$ 个灯泡以这两种方式放置在不同的顶点上,则两种方式被认为是不同的。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$; $$$1 \le k \lt n$$$) - 树中的顶点数和两个连续灯泡之间的距离约束。

第二行包含 $$$n-1$$$ 整数 $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i \lt i$$$),其中 $$$p_i$$$ 是树中第 $$$i$$$ 个顶点的父顶点。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数——在遵循所有规则的情况下悬挂花环的方式数量,以 $$$998244353$$$ 为模。

示例

输入
复制

4
5 1
1 1 2 2
5 2
1 1 2 2
5 3
1 1 2 2
8 4
1 1 3 2 3 1 4

输出
复制

0
2
4
12