A16839 · Short Garland

题目描述

Monocarp 想要在圣诞树上悬挂一串彩灯。 圣诞树是一棵有 $n$ 个结点、以结点 $1$ 为根的树。树上两个结点之间的距离是它们之间最短路径上的边数，一个结点的深度是它到根的距离。 这串彩灯由 $n$ 个灯泡通过导线连接组成，灯泡编号从 $1$ 到 $n$，每两个相邻灯泡之间的导线长度为 $k$。 彩灯必须按照如下规则悬挂在树上： - 每个灯泡必须放在树的一个结点上，并且每个结点恰好有一个灯泡； - 灯泡 $1$ 必须放在树的根结点上； - 每个后续灯泡都必须放在它的父结点已经放有灯泡的结点上。如果有多个这样的结点，选择深度最大的那个；如果仍有多个，可以任选其一； - 对于每对相邻的两个灯泡，它们所放置结点之间的距离不能超过 $k$。 你的任务是计算有多少种悬挂彩灯的方案，需要输出方案数对 $998244353$ 取模的结果。如果存在至少一个 $i\in [1, n]$，使得两种方案下第 $i$ 个灯泡放在不同结点上，则认为这两种方案不同。

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 3 \cdot 10^5$；$1 \le k < n$）——树的结点数和相邻灯泡的距离上限。 第二行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$（$1 \le p_i < i$），其中 $p_i$ 表示第 $i$ 个结点的父结点编号。 输入额外保证：所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每组测试用例，输出一个整数——所有满足条件的悬挂彩灯方案数量，对 $998244353$ 取模。

输入 #1

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

输出 #1