Hide

Problem J
Association of Cats and Magical Lights

Rar the Cat$^($$^)$ is the founder of ACM (Association of Cats and Magical Lights). This is the story of the founding of ACM.

It is the second half of the year again and Rar the Cat$^($$^)$ is looking forward to Christmas. When people think of Christmas, Christmas trees will surely come into the picture. This year, Rar the Cat$^($$^)$ decides to decorate a Christmas tree with $N$ LED lights with up to 100 different colours. Each LED light can only have a single colour as Rar the Cat$^($$^)$ is too poor to afford more sophisticated models of LED lights.

Being a programmer himself, Rar the Cat$^($$^)$ LED lights are arranged in a tree formation on the Christmas tree. That being said, each LED light can be represented as a node and the wires between $2$ LED lights can be represented as an edge. The whole formation consists of $N$ nodes fully connected by $N-1$ edges. The nodes are labelled from $1$ to $N$ and each node can hold colour denoted as $1$ to $100$. It is noted that each LED is connected to every other LED directly or indirectly by wires and the tree formed is rooted at node $1$.

Hubert the Cow finds that Rar the Cat$^($$^)$ Christmas tree is too boring because it lacks some magical colours. A magical colour in a subtree is defined as a colour whereby there is an odd number of LEDs with that particular colour within the subtree only.

/problems/magicallights/file/statement/en/img-0001.png
In the tree to the right, the subtree of node $1$ has $3$ white nodes and $4$ black nodes. As such, white is a magical colour for the subtree of node $1$. However, the subtree of node $3$ has $1$ white node and $1$ black node, thus the number of magical colour of the subtree of node $3$ is $2$. In addition, all leaf nodes of the tree have $1$ magical colour by definition.

In order to improve on his Christmas tree decorations, Rar the Cat$^($$^)$ intends to modify the colours of the LED lights on the tree. However, he does not know how to count how many magical colours there are.

Your task, is now to answer how many magical colours there are in a subtree requested by Rar the Cat$^($$^)$. This will be done in between Rar the Cat$^($$^)$ modifications. There will be $Q$ queries and modifications in total.

Soon after this, Rar the Cat$^($$^)$ Christmas tree with these magical lights become so popular and Rar the Cat$^($$^)$ founded ACM to further spread the adoption of such trees worldwide.

Input

The first line will consists of $2$ integers, $N$ and $Q$. $N$ will be positive and not more than $300\, 000$ while $Q$ will be positive and not more than $1\, 000\, 000$.

$N$ integers will follow on the next line. The $i^{th}$ integer will be $C_ i$. $C_ i$ denotes the colour of node $i$ and can only range from $1$ to $100$ inclusive.

The next line will have $N-1$ integers. The $i^{th}$ integer will be $P_{i+1}$, $P_{i+1}$ denotes the parent node of node $i+1$.

$Q$ lines will then follow with $2$ integers each, $K$ followed by $X$. If $K$ is $0$, then this line represents a query for how many magical colours are there in the subtree of node $X$. If $K$ is an integer between $1$ and $100$, then it means that the colour of node $X$ is changed to colour $K$.

Output

For each query when $K = 0$, output in one line: the number of magical colours in the subtree of $X$ (inclusive).

Sample Input 1 Sample Output 1
10 5
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9
0 1
0 4
1 4
0 1
0 4
10
7
8
7

Sample Input 2 Sample Output 2
7 7
1 2 2 1 1 2 1
1 1 1 2 2 3
0 1
0 2
0 3
0 4
0 5
0 6
0 7
1
1
2
1
1
1
1

Please log in to submit a solution to this problem

Log in