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 < 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). 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 < 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 < 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. For each test case, output one integer — the number of permutations modulo (998\,244\,353). Visualizer link In the first test case, the only permutation whic