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

Ryan 有一棵 $N$ 个节点的有根树，每个节点上写有一个数字 $0$ 或 $1$。 Ryan 的朋友也有一棵有根树，每个节点上写有一个数字 $0$ 或 $1$。设这棵树的节点数为 $M$。 Ryan 想将这 $N + M$ 个节点排成水平的一行。这里，对于每个节点，不允许它的任何祖先出现在它的右侧。注意，Ryan 的树中的节点与他朋友的树中的节点之间没有任何约束。 排列好节点后，令 $X$ 为从左到右读取节点上数字得到的序列。Ryan 希望最小化 $X$ 的**逆序数**。请求出 $X$ 可能的最小逆序数。 由于 Ryan 有 $Q$ 个朋友，请对每个朋友分别解决上述问题。 朋友树上节点所写的数字是以加密形式给出的。具体细节请参见输入格式部分的说明。

输入包含一个测试用例，格式如下。 $$ \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} $$ 第一行包含一个整数 $N$（$1 \leq N \leq 200\,000$），表示 Ryan 的树的节点数。 第二行包含 $N - 1$ 个整数。每个 $P_i$（$2 \leq i \leq N$，$1 \leq P_i < i$）表示节点 $i$ 的父节点是节点 $P_i$。注意节点 $1$ 是树的根，$P_1$ 未给出。 第三行包含 $N$ 个整数。每个 $V_i$（$1 \leq i \leq N$，$0 \leq V_i \leq 1$）表示写在节点 $i$ 上的数字。 第四行包含一个整数 $Q$（$1 \leq Q \leq 100\,000$），表示 Ryan 的朋友数量。 对于每个朋友 $k$（$1 \leq k \leq Q$），他们的树的信息按以下格式给出： - 第一行包含一个整数 $M_k$（$1 \leq M_k$），表示第 $k$ 个朋友的树的节点数。 - 第二行包含 $M_k - 1$ 个整数。每个 $P_{k,i}$（$2 \leq i \leq M_k$，$1 \leq P_{k,i} < i$）表示节点 $i$ 的父节点是节点 $P_{k,i}$。注意节点 $1$ 是树的根，$P_{k,1}$ 未给出。 - 第三行包含 $M_k$ 个整数。每个 $U_{k,i}$（$1 \leq i \leq M_k$，$0 \leq U_{k,i} \leq 1$）表示第 $k$ 个朋友的树上节点 $i$ 的**加密**数字。 此外，所有 $M_k$（$1 \leq k \leq Q$）的总和不超过 $200\,000$。 ### 解密朋友树上节点的数字 令 $X_0 = 0$，对于每个朋友 $k$（$1 \leq k \leq Q$），令 $X_k$ 表示第 $k$ 个朋友的答案。第 $k$ 个朋友的树上节点 $i$ 所写的**实际**值 $V_{k,i}$（$1 \leq k \leq Q$，$1 \leq i \leq M_k$，$0 \leq V_{k,i} \leq 1$）由以下公式确定： $$ V_{k,i} = (\text{powmod}(X_{k-1}, i, 998244353) + U_{k,i}) \mod 2. $$ 这里，$\text{powmod}(a, b, m)$ 表示 $(a^b \mod m)$。

输出 $Q$ 行。第 $i$ 行应包含一个整数，表示 Ryan 与他的第 $i$ 个朋友对应的最小可能逆序数。

解密后的样例如下所示： ``` 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 ``` 翻译由 DeepSeek V3.2 完成