题目描述

这是本题的困难版本。两个版本的区别在于，此版本中 $n \leq 5 \cdot 10^{5}$。只有解决了本题的所有版本才能进行黑客攻击。

给定一棵根节点为 $1$、包含 $n$ 个顶点的树 $T$ 和一个长度为 $n$ 的序列 $a$，请计算满足以下条件的排列 $p$ 的数量：

• 对于所有 $1 \leq u \leq n$，恰好存在 $a_u$ 个顶点 $v$，满足 $v$ 是 $u$ 在树 $T$ 上的祖先且 $p_{v} < p_{u}$。

输出答案对 $998244353$ 取模的结果。输入数据经过特殊选择，保证至少存在一个有效的排列。

• 一个长度为 $n$ 的排列是一个由 $1$ 到 $n$ 的 $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 \times 10^5$) - 表示顶点数。

每个测试用例的第二行包含 $n-1$ 个整数 $fa_2, fa_3, \dots, fa_n$ ($1 \leq fa_i \leq n$) - $fa_i$ 是节点 $i$ 在树 $T$ 上的父节点。

每个测试用例的第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \leq a_i \leq n$)。

保证所有测试用例的 $n$ 的总和不超过 $5 \cdot 10^5$。输入数据经过特殊选择，保证至少存在一个有效的排列。

输出格式

对于每个测试用例，输出一个整数 — 排列的数量对 $998244353$ 取模的结果。

样例

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]$。

数据范围

前 $40\%$ 的数据，保证所有样例的 $n$ 之和不会超过 $5000$。

$100\%$ 的数据，见输入格式。