F2. Ранг префикса цепи (сложная версия)
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии $$$n \le 5 \cdot 10^5$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Дано дерево $$$T$$$ с $$$n$$$ вершинами, корень которого находится в $$$1$$$, и последовательность $$$a$$$ длины $$$n$$$. Необходимо подсчитать количество перестановок$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n$$$, которые удовлетворяют следующему условию:

  • Для всех $$$1 \le u \le n$$$ существует ровно $$$a_u$$$ вершин $$$v$$$, таких что $$$v$$$ является предком $$$u$$$ в $$$T$$$ и $$$p_v \lt p_u$$$.

Выведите ответ по модулю $$$998\,244\,353$$$. Входые данные выбраны таким образом, что существует хотя бы одна допустимая перестановка.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — количество вершин.

Вторая строка каждого набора содержит $$$n-1$$$ целых числа $$$fa_2,fa_3,\ldots,fa_n$$$ ($$$1 \le fa_i \lt i$$$) — $$$fa_i$$$ является родителем $$$i$$$ в $$$T$$$.

Третья строка каждого набора содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \lt n$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$5 \cdot 10^5$$$. Входые данные выбраны таким образом, что существует хотя бы одна допустимая перестановка.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество перестановок по модулю $$$998\,244\,353$$$.

Пример
Входные данные
3
5
1 2 3 4
0 1 2 3 4
5
1 2 1 1
0 1 0 0 0
8
1 1 3 3 4 5 7
0 0 1 0 1 3 3 1
Выходные данные
1
6
4
Примечание

Ссылка на визуализатор.

В первом наборе входных данных единственной перестановкой, которая удовлетворяет условию, является $$$[1,2,3,4,5]$$$.

Во втором наборе перестановками, которые удовлетворяют условию, являются $$$[4,5,1,2,3],[4,5,1,3,2],[4,5,2,1,3],[4,5,2,3,1],[4,5,3,1,2],[4,5,3,2,1]$$$.

В третьем наборе перестановками, которые удовлетворяют условию, являются $$$[3,1,6,2,5,7,8,4],[3,1,6,2,5,8,7,4],[3,2,6,1,5,7,8,4],[3,2,6,1,5,8,7,4]$$$.