P10180 Semi-Color Trio

 FanFan is not satisfied with building only a deep-blue tree. He thinks a tree with only deep blue is too monotonous, so he wants to dye this tree with colors.

Since it is now the fantasy Year of the Dragon, FanFan’s deep-blue tree has been dyed with colors, and the color of node $i$ is $a_i$. FanFan is someone who changes his mind easily. In the next $q$ days, he will change the colors he likes every day. On day $i$, the two colors he likes are $x_i, y_i$ ($x_i \neq y_i$). But to take care of his tree, he needs to move on the tree often, and he will only pass through colors he likes. Specifically, on day $i$, FanFan will choose an ordered pair of nodes $(u,v)$, then move along the unique simple path $u \to v$, and all nodes on the path (including $u$ and $v$) must have colors in $\{x_i, y_i\}$ ($u$ may be equal to $v$). After that, he can do one Yoimiya pull. Every day, you need to pull a C6 Yoimiya, and then tell FanFan how many possible ordered node pairs he can choose.

The first line contains two positive integers $n, q$. The next line contains $n$ positive integers $a_1, a_2, \cdots, a_n$, representing the color of each node. The next line contains $n-1$ positive integers $p_2, p_3, \cdots, p_n$, meaning that for all $2 \le i \le n$, there is an edge $(p_i, i)$ in the tree. The next $q$ lines each contain two positive integers $x_i, y_i$.

For each query, output one positive integer per line representing the answer.

### Sample $1$ Explanation The shape of the tree is shown in the figure:  For the first query, the only valid paths are paths from one node to another among $\{1,2,3\}$. For the second query, the only valid paths are $1 \to 1, 1 \to 3, 3 \to 1, 3 \to 3, 4 \to 4, 5 \to 5$. ### Subtask Constraints This problem uses bundled subtasks. For $100\%$ of the data, $1 \le n \le 10^6$, $1 \le q \le 2 \times 10^6$, $1 \le a_i, x, y \le n$, $x \neq y$. It is guaranteed that $p_i < i$. | Subtask ID | $n$ | $q$ | Special Property | Score | Dependencies | | :--------: | :----------------: | :----------------: | :--------------: | :---: | :----------: | | Subtask \#1 | $\le 100$ | $\le 100$ | None | $7$ | None | | Subtask \#2 | $\le 2000$ | $\le 2000$ | None | $18$ | $1$ | | Subtask \#3 | $\le 10^5$ | $\le 2\times 10^5$ | A | $5$ | None | | Subtask \#4 | $\le 10^5$ | $\le 2\times 10^5$ | B | $19$ | None | | Subtask \#5 | $\le 10^5$ | $\le 2\times 10^5$ | None | $21$ | $1,2,3,4$ | | Subtask \#6 | $\le 2\times 10^5$ | $\le 5\times 10^5$ | None | $10$ | $5$ | | Subtask \#7 | $\le 10^6$ | $\le 2\times 10^6$ | None | $20$ | $6$ | Special Property A: $p_i = 1$. Special Property B: $p_i = i - 1$. Translated by ChatGPT 5