Задано корневое дерево, состоящее из $$$n$$$ вершин. Вершины в дереве пронумерованы от $$$1$$$ до $$$n$$$, корень дерева – вершина $$$1$$$. Пусть $$$d_x$$$ — это расстояние (количество ребер на кратчайшем пути) от корня до вершины $$$x$$$.
Есть фишка, которая изначально расположена в корне. Вы можете выполнять следующую операцию столько раз, сколько захотите (возможно, ноль):
Например, в приведённом выше дереве возможны следующие перемещения фишки: $$$1 \rightarrow 2$$$, $$$1 \rightarrow 5$$$, $$$2 \rightarrow 7$$$, $$$5 \rightarrow 3$$$, $$$5 \rightarrow 4$$$, $$$3 \rightarrow 6$$$, $$$7 \rightarrow 6$$$.
Последовательность вершин является допустимой, если вы можете перемещать фишку таким образом, чтобы она посетила все вершины из последовательности (и только их), в порядке, в котором они даны в последовательности.
Ваша задача — вычислить количество допустимых последовательностей вершин. Поскольку ответ может быть большим, выведите его по модулю $$$998244353$$$.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$).
Вторая строка содержит $$$n-1$$$ целых числа $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i < i$$$), где $$$p_i$$$ — это родитель $$$i$$$-й вершины в дереве. Вершина $$$1$$$ является корнем.
Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превышает $$$3 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — количество допустимых последовательностей вершин, взятое по модулю $$$998244353$$$.
341 2 131 271 2 2 1 4 5
4 2 8
В первом примере допустимы следующие последовательности: $$$[1]$$$, $$$[1, 2]$$$, $$$[1, 4]$$$, $$$[1, 4, 3]$$$.
Во втором примере допустимы следующие последовательности: $$$[1]$$$, $$$[1, 2]$$$.
В третьем примере допустимы следующие последовательности: $$$[1]$$$, $$$[1, 2]$$$, $$$[1, 2, 7]$$$, $$$[1, 2, 7, 6]$$$, $$$[1, 5]$$$, $$$[1, 5, 3]$$$, $$$[1, 5, 3, 6]$$$, $$$[1, 5, 4]$$$.
Название |
---|