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 < 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](https://codeforces.com/assets/contests/2164/F_ahVa9noocebeero5shie.html) 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] $ .