Tree and Queries 19

A tree with $N$ vertices is given. A tree is a connected graph with no undirected cycles. The vertices are numbered from $1$ to $N$, and each vertex is either black or white.

Write a program that processes the following queries.

• $X$: Flip the color of vertex $X$ (white becomes black, and black becomes white). Then, for every pair $(a, b)$ of distinct white vertices, output the sum of the levels of their LCA (lowest common ancestor).

Vertex $1$ is the root. The level of the root is $0$, and the level of any other vertex is the level of its parent plus $1$.

The first line contains $N$ and $Q$, the number of vertices and the number of queries.

The second line contains integers $t_1, t_2, \cdots, t_N$, the colors of vertices $1$ through $N$. $t_i = 0$ means black, and $t_i = 1$ means white.

The third line contains $P_2, P_3, \cdots, P_N$, the parent of each vertex from $2$ through $N$.

Each of the next $Q$ lines contains one query $X$.

The first line contains the answer for the initial state. From the second line on, the next $Q$ lines each contain the answer for one query.

• $2 \le N \le 5 \times 10^5$
• $1 \le Q \le 5 \times 10^5$
• For $1 \le i \le N$, $0 \le t_i \le 1$
• For $2 \le i \le N$, $1 \le P_i < i$
• $1 \le X \le N$