这是问题的困难版本。版本之间的区别在于,在这个版本中,$$$n \le 5 \cdot 10^5$$$。只有解决了该问题的所有版本,您才能破解。
给定一棵树$$$T$$$,其$$$n$$$顶点以$$$1$$$为根,序列$$$a$$$长度为$$$n$$$,计算满足以下条件的长度$$$n$$$的排列$$$^{\text{*}}$$$ $$$p$$$的数量:
- 对于所有 $$$1 \le u \le n$$$,恰好存在 $$$a_u$$$ 顶点 $$$v$$$,使得 $$$v$$$ 是 $$$T$$$ 和 $$$p_v \lt p_u$$$ 中 $$$u$$$ 的祖先。
输出对 $$$998\,244\,353$$$ 取模的答案。以这种方式选择输入数据,以保证至少存在一种有效排列。
$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$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$$$ 是 $$$T$$$ 上 $$$i$$$ 的父级。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \lt n$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。以这种方式选择输入数据,以保证至少存在一种有效排列。
输出
对于每个测试用例,输出一个整数 — 排列数以 $$$998\,244\,353$$$ 为模。
示例
输入复制
351 2 3 40 1 2 3 451 2 1 10 1 0 0 081 1 3 3 4 5 70 0 1 0 1 3 3 1
输出复制
164
注意
展示台链接
在第一个测试用例中,满足条件的唯一排列是$$$[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]$$$。