409364: GYM103492 A Median Problem

We consider an integer $$$x$$$ as the median of a set $$$A$$$ containing $$$n$$$ distinct integers if it meets the following conditions:

• $$$x \in A$$$
• There are at least $$$\lfloor\frac{n+1}{2}\rfloor$$$ integers greater than or equal to $$$x$$$ in set $$$A$$$.
• There are at least $$$\lfloor\frac{n+1}{2}\rfloor$$$ integers less than or equal to $$$x$$$ in set $$$A$$$.

$$$\lfloor y \rfloor$$$ means the largest integer that does not exceed $$$y$$$. For example, if $$$A=\{1,3,4,5,7,9\}$$$, then either $$$4$$$ or $$$5$$$ is the median of set $$$A$$$.

Given a tree with $$$n$$$ nodes rooted at node $$$1$$$. Each node $$$u$$$ has an associated value $$$a_u$$$, where $$$a_1, a_2, \ldots, a_n$$$ is a permutation of $$$n$$$ (every integer from $$$1$$$ to $$$n$$$ occurs exactly once). Each node $$$u$$$ has another value $$$b_u$$$ satisfying the following condition:

• $$$b_u$$$ is the median of the set $$$\{ a_u \} \cup \{b_v \mid \text{node } u \text{ is the parent of node } v\}$$$. (The parent of node $$$v$$$ is the node directly connected to $$$v$$$ on the path to the root.)

Unfortunately, you forget some of $$$a_i$$$ and all $$$b_i$$$ except $$$b_1$$$. Now you are wondering how many different permutations $$$a_1,a_2,\dots,a_n$$$ that can match the $$$a_i$$$ and $$$b_1$$$ you remember when the tree satisfies the condition above. We consider two permutations $$$p_1,p_2,\dots,p_n$$$ and $$$q_1,q_2,\dots,q_n$$$ different if there exists an index $$$i$$$ satisfying $$$p_i \neq q_i$$$.

You are required to calculate the number of different permutations $$$a_1,a_2,\dots,a_n$$$ modulo $$$998244353$$$, for each $$$b_1 \in [1, n]$$$ respectively.

The first line of the input contains an integer $$$T$$$ $$$(1 \leq T \leq 80)$$$, representing the number of test cases.

The first line of each test case contains an integer $$$n$$$ $$$(2 \leq n \leq 80)$$$, representing the number of nodes.

The second line of each test case contains $$$n - 1$$$ integers $$$p_2, p_3, \ldots, p_n \ (1 \leq p_i < i)$$$, where $$$p_i$$$ represents the parent of node $$$i$$$.

The third line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n \ (0 \leq a_i \leq n)$$$, representing the value of each node. $$$a_i = 0$$$ means you forget $$$a_i$$$. It is guaranteed that all non-zero $$$a_i$$$ are distinct.

It is guaranteed that there are at most $$$5$$$ test cases satisfying $$$n > 10$$$.

For each test case, output a single line containing $$$n$$$ integers, the $$$k$$$-th of which is the answer when $$$b_1 = k$$$.

Don't print any extra spaces at the end of each line.

2
4
1 1 1
0 0 0 2
5
1 1 2 2
0 0 1 5 0

0 6 6 0
0 2 4 0 0