CF2182G.Short Garland

Monocarp wants to hang a garland on the Christmas tree.

The Christmas tree is a tree with $n$ vertices rooted at vertex $1$. The distance between two vertices of the tree is the number of edges on the shortest path between them, and the depth of a vertex is the distance from it to the root.

The garland consists of $n$ bulbs connected by wire and numbered from $1$ to $n$. The length of the wire between every two adjacent bulbs is $k$.

The garland must be hung on the tree according to the following rules:

• every bulb must be placed on one of the vertices of the tree, and every vertex must have exactly one bulb on it;
• bulb $1$ must be placed on the root of the tree;
• each subsequent bulb has to be placed on such a vertex that its parent vertex has a bulb on it. If there are multiple such vertices, the vertex with the largest depth is chosen. If there are still multiple options, any of them can be chosen;
• for each pair of subsequent bulbs, the distance between the vertices they are placed on must not exceed $k$.

Your task is to count the number of ways to hang the garland while following all the rules and output it modulo $998244353$. Two ways are considered different if there exists at least one integer $i \in [1, n]$ such that the $i$-th bulb is placed on different vertices in these two ways.

Monocarp 想要在一棵圣诞树上悬挂一串彩灯。

这棵圣诞树是一棵含 $n$ 个顶点的有根树，根节点为顶点 $1$。树中两个顶点之间的距离定义为它们之间最短路径上的边数；一个顶点的深度定义为该顶点到根节点的距离。

这串彩灯由 $n$ 个灯泡通过导线连接而成，灯泡编号为 $1$ 至 $n$。每两个相邻灯泡之间的导线长度为 $k$。

彩灯必须按照以下规则悬挂在树上：

• 每个灯泡必须放置在树的一个顶点上，且每个顶点上恰好放置一个灯泡；
• 灯泡 $1$ 必须放置在树的根节点上；
• 对于后续每一个灯泡（即编号为 $i = 2, 3, \dots, n$ 的灯泡），它必须被放置在一个父节点已放置有灯泡的顶点上；若存在多个满足条件的顶点，则选择其中深度最大的那个；若仍存在多个候选顶点，则可任选其一；
• 对于每一对相邻编号的灯泡（即灯泡 $i$ 和灯泡 $i+1$，其中 $i = 1, 2, \dots, n-1$），它们所放置的顶点之间的距离不得超过 $k$。

你的任务是计算所有满足上述全部规则的悬挂方式总数，并将结果对 $998244353$ 取模后输出。若存在某个整数 $i \in [1, n]$，使得在这两种方式中第 $i$ 个灯泡被放置在不同的顶点上，则认为这两种方式不同。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($2 \le n \le 3 \cdot 10^5$; $1 \le k \lt n$) — the number of vertices in the tree and the distance constraint between two consecutive bulbs.

The second line contains $n-1$ integers $p_2, p_3, \dots, p_n$ ($1 \le p_i \lt i$), where $p_i$ is the parent of the $i$-th vertex in the tree.

Additional constraint on the input: the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, output one integer — the number of ways to hang the garland while following all the rules, modulo $998244353$.

对于每个测试用例，输出一个整数——在遵守所有规则的前提下悬挂彩灯的方式数目，对 $998244353$ 取模。