CF2164F2.Chain Prefix Rank (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, $n \le 5 \cdot 10^5$. You can hack only if you solved all versions of this problem.

Given a tree $T$ with $n$ vertices rooted at $1$ and a sequence $a$ of length $n$, count the number of permutations$^{\text{∗}}$ $p$ of length $n$ that satisfy the following condition:

• For all $1 \le u \le n$, there are exactly $a_u$ vertices $v$ such that $v$ is an ancestor of $u$ in $T$ and $p_v \lt p_u$.

Output the answer modulo $998\,244\,353$. Input data is selected in such way, such that it's guaranteed that at least one valid permutation exists.

$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

这是该问题的困难版本。两个版本的区别在于，在本版本中，$n \le 5 \cdot 10^5$。仅当您已解决该问题的所有版本时，才可进行 Hack。

给定一棵以 $1$ 为根、含 $n$ 个顶点的树 $T$，以及一个长度为 $n$ 的序列 $a$，请计算满足以下条件的排列$^{\text{∗}}$ $p$（长度为 $n$）的个数：

• 对所有 $1 \le u \le n$，恰好存在 $a_u$ 个顶点 $v$，使得 $v$ 是 $u$ 在树 $T$ 中的祖先，且 $p_v \lt p_u$。

输出答案对 $998\,244\,353$ 取模的结果。输入数据经过选取，保证至少存在一个合法的排列。

$^{\text{∗}}$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 中 $n$ 个互不相同的整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，而 $[1,2,2]$ 不是排列（数字 $2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中包含了 $4$）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5000$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($2 \le n \le 5 \cdot 10^5$) — the number of vertices.

The second line of each test case contains $n-1$ integers $fa_2,fa_3,\ldots,fa_n$ ($1 \le fa_i \lt i$)— $fa_i$ is the parent of $i$ on $T$.

The third line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \le a_i \lt n$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$. Input data is selected in such way, such that it's guaranteed that at least one valid permutation exists.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$ 表示树 $T$ 中顶点 $i$ 的父节点。

每个测试用例的第三行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0 \le a_i \lt n$）。

保证所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$。输入数据经过选取，以确保至少存在一个合法的排列。

For each test case, output one integer — the number of permutations modulo $998\,244\,353$.

对于每个测试用例，输出一个整数——排列数对 $998\,244\,353$ 取模的结果。

Visualizer link

In the first test case, the only permutation which satisfies the condition is $[1,2,3,4,5]$.

In the second test case, permutations which satisfy the condition are $[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]$.

In the third test case, permutations which satisfy the condition are $[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]$.

可视化链接

在第一个测试用例中，唯一满足条件的排列是 $[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]$。