Tree Colors and Queries 2

A tree with $N$ vertices is given. The vertices are numbered 1 to $N$, and each vertex has a color, which is a natural number from 1 to 100,000. Vertex 1 is the root. Since the graph is a tree, there is exactly one path between any two distinct vertices.

If a path between $u$ and $v$ exists, you can go from $u$ to $v$.

You must process two kinds of queries.

• 1 a: Remove the edge connecting vertex $a$ and its parent. This query is only given when that edge exists.
• 2 a: Looking only at the vertices you can reach from vertex $a$, print the number of distinct colors.

The first line contains $N$ ($1 \le N \le 100{,}000$) and $Q$ ($1 \le Q \le 1{,}000{,}000$), the number of vertices and the number of type 2 queries. The second line has $N-1$ integers. The $i$-th integer is the parent of vertex $i+1$. The third line has $N$ integers. The $i$-th integer is the color of vertex $i$. The next $N+Q-1$ lines contain the queries: $N-1$ of type 1 and $Q$ of type 2. Each query is a line with its type $X$ ($1 \le X \le 2$) and a non-negative integer $k$. The vertex $a$ to process is $k \oplus \mathrm{lst}$, and $1 \le a \le N$. $\oplus$ is bitwise XOR. $\mathrm{lst}$ is the result of the most recent type 2 query, and its initial value is 0.

For each of the $Q$ type 2 queries, print the answer on its own line, in order.