P15774 [JAG 2025 Summer Camp #2] Double 01 on Tree

Ryan has a rooted tree with $N$ vertices, where each vertex is written with a number $0$ or $1$. Ryan's friend also has a rooted tree, where each vertex is written with a number $0$ or $1$. Let the number of vertices in this tree be $M$. Ryan wants to arrange these $N + M$ vertices in a horizontal row. Here, for every vertex, there should be no ancestor of that vertex to the right of that vertex. Note that there are no constraints between the vertices in Ryan's tree and the vertices in his friend's tree. After arranging the vertices, let $X$ be the sequence obtained by reading the numbers written on the vertices from left to right. Ryan wants to minimize the inversion number of $X$. Find the minimum possible inversion number of $X$. Since Ryan has $Q$ friends, solve the above problem for each of his friends. The numbers written on the vertices of Ryan's friends' trees are given in an encrypted form. See the bottom of the Input section for details.

The input consists of a single test case of the following format. $$ \begin{aligned} & N \\ & P_2 \ P_3 \ \ldots \ P_N \\ & V_1 \ V_2 \ \ldots \ V_N \\ & Q \\ & M_1 \\ & P_{1,2} \ P_{1,3} \ \ldots \ P_{1,M_1} \\ & U_{1,1} \ U_{1,2} \ \ldots \ U_{1,M_1} \\ & M_2 \\ & P_{2,2} \ P_{2,3} \ \ldots \ P_{2,M_2} \\ & U_{2,1} \ U_{2,2} \ \ldots \ U_{2,M_2} \\ & \vdots \\ & M_Q \\ & P_{Q,2} \ P_{Q,3} \ \ldots \ P_{Q,M_Q} \\ & U_{Q,1} \ U_{Q,2} \ \ldots \ U_{Q,M_Q} \end{aligned} $$ The first line contains an integer $N$ ($1 \leq N \leq 200\,000$) representing the number of vertices in Ryan's tree. The second line contains $N - 1$ integers. Each $P_i$ ($2 \leq i \leq N$, $1 \leq P_i < i$) represents that the parent of vertex $i$ is vertex $P_i$. Note that vertex $1$ is the root of the tree and $P_1$ is not given. The third line contains $N$ integers. Each $V_i$ ($1 \leq i \leq N$, $0 \leq V_i \leq 1$) represents that the number written on vertex $i$. The fourth line contains an integer $Q$ ($1 \leq Q \leq 100\,000$) representing the number of Ryan's friends. For each friend $k$ ($1 \leq k \leq Q$), the input for their tree is given in the following format: - The first line contains an integer $M_k$ ($1 \leq M_k$), representing the number of vertices in the $k$-th friend's tree. - The second line contains $M_k - 1$ integers. Each $P_{k,i}$ ($2 \leq i \leq M_k$, $1 \leq P_{k,i} < i$) represents that the parent of vertex $i$ is vertex $P_{k,i}$. Note that vertex $1$ is the root of the tree and $P_{k,1}$ is not given. - The third line contains $M_k$ integers. Each $U_{k,i}$ ($1 \leq i \leq M_k$, $0 \leq U_{k,i} \leq 1$) represents the encrypted number written on vertex $i$ of the $k$-th friend's tree. Additionally, the sum of the $M_k$ ($1 \leq k \leq Q$) does not exceed $200\,000$. ### Decrypting the Numbers on the Vertices of Ryan’s Friends' Trees Let $X_0 = 0$, and for each friend $k$ ($1 \leq k \leq Q$), let $X_k$ denote the answer for the $k$-th friend. The actual value $V_{k,i}$ ($1 \leq k \leq Q$, $1 \leq i \leq M_k$, $0 \leq V_{k,i} \leq 1$) written on vertex $i$ of the $k$-th friend's tree is determined as follows: $$ V_{k,i} = (\text{powmod}(X_{k-1}, i, 998244353) + U_{k,i}) \mod 2. $$ Here, $\text{powmod}(a, b, m)$ denotes $(a^b \mod m)$.

Print $Q$ lines. The $i$-th line should contain a single integer, representing the minimum possible inversion number for Ryan and his $i$-th friend.

The decrypted values corresponding to this sample are shown below ``` 6 1 1 2 3 3 0 1 1 0 0 0 4 4 1 2 2 1 0 1 0 6 1 1 2 3 3 0 0 1 1 0 1 1 1 15 1 2 3 2 5 6 2 2 9 10 1 12 13 12 1 1 1 0 1 1 0 0 1 0 0 1 1 0 1 ```