CF2164F2 Chain Prefix Rank (Hard Version)

这是该问题的难度较高版本。不同之处在于，本题中 $n \leq 5 \cdot 10^5$。仅当你解决了该问题的所有版本后，才能进行 Hack。 给定一棵有 $n$ 个结点、以 $1$ 号结点为根的树 $T$，以及一个长度为 $n$ 的序列 $a$，请统计有多少个长度为 $n$ 的排列 $p$ 满足如下条件： - 对于所有 $1 \leq u \leq n$，恰好有 $a_u$ 个结点 $v$ 满足 $v$ 是树 $T$ 中 $u$ 的祖先，且 $p_v < p_u$。 输出方案数对 $998\,244\,353$ 取模的结果。输入数据保证至少存在一个合法的排列。 $^\text{∗}$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 的所有整数恰好出现一次组成的序列。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$n=3$ 却有 $4$ 出现）。

每组数据包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 5000$），表示测试用例数。 接下来依次描述每个测试用例： 第一行为一个整数 $n$（$2 \leq n \leq 5 \cdot 10^5$），表示树的结点数。 第二行为 $n-1$ 个整数 $fa_2,fa_3,\ldots,fa_n$（$1 \leq fa_i < i$），其中 $fa_i$ 表示节点 $i$ 在树 $T$ 中的父节点。 第三行为 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0 \leq a_i < n$）。 保证所有测试用例中的 $n$ 之和不超过 $5 \cdot 10^5$。输入数据保证至少存在一个合法的排列。

对于每个测试用例，输出一个整数，表示合法排列的方案数，答案需对 $998\,244\,353$ 取模。

[可视化链接](https://codeforces.com/assets/contests/2164/F_ahVa9noocebeero5shie.html) 在第一个样例中，唯一满足条件的排列为 $[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]$。 由 ChatGPT 5 翻译