P15734 [JAG 2024 Summer Camp #2] Flip Path on Rooted Tree

You are given a rooted tree with $N$ vertices, with vertex $1$ as the root. The parent of vertex $i$ ($2 \leq i \leq N$) is vertex $p_i$. Each vertex has a value of either $0$ or $1$ written on it, and initially, vertex $i$ ($1 \leq i \leq N$) has the value $a_i$ written on it. You need to handle $Q$ queries. The $i$-th query ($1 \leq i \leq Q$) is as follows: - If the value written on vertex $x_i$ is $0$, change it to $1$; if it is $1$, change it to $0$. After that, output the answer to the following problem: - Find the minimum number of operations required to make all vertices have the value $0$ by repeatedly performing the following operation: - Select a vertex. For every vertex on the path from vertex $1$ to the selected vertex (inclusive), change the value to $1$ if it is $0$, and to $0$ if it is $1$. It can be proved that this can be achieved in a finite number of operations.

The input is given in the following format: $$ \begin{aligned} &N \\ &p_2 \ p_3 \ \ldots \ p_N \\ &a_1 \ a_2 \ \ldots \ a_N \\ &Q \\ &x_1 \\ &x_2 \\ &\vdots \\ &x_Q \end{aligned} $$ - $2 \leq N \leq 200,000$ - $1 \leq Q \leq 200,000$ - $1 \leq p_i < i \ (2 \leq i \leq N)$ - $0 \leq a_i \leq 1 \ (1 \leq i \leq N)$ - $1 \leq x_i \leq N \ (1 \leq i \leq Q)$ - All input values are integers.

Output $Q$ lines. On the $i$-th line, output the answer to the $i$-th query.