Background

I am going to cast magic on you, Mr. Undead. I hope you can see more wonderful things. I hope you can experience more things that I cannot experience. I hope... your heart... no matter how many times, can be resu—

......

Your magic is too late. It is the same as knowing there is no way to save you, as if it were just like this empty sky—

Stars?

......

Where are the stars? There is a star-shaped star floating in the sky?

It is like that strange thing, a product of Superman Machinery.

......

I can no longer keep only chasing stars...

The true body of the undead is indeed not necessarily on that star. I also know that most of them are dangerous missions outside the usual rules. I understand all of this...

But that kind of star is floating in the sky. Superman Machinery might be up there, and prehistoric wisdom must be piled up like mountains.

......

The reason for the star shape is a mystery, and there is no obvious necessity from an engineering point of view. But if it was built based on natural objects, then this shape makes sense.

To be precise, I think it is a group rather than a single life form. And if it is a living creature, then we can expect it to have advantages that machines do not have, such as naturally repairing damaged parts, solving long-term aging problems through reproduction, and it might even be made on the premise that no manager is needed.

At present, we still do not understand what system it uses to maintain its flight orbit, but its altitude should be the best environment.

A super-intelligent entity that can even cross the wall of dimensions, how could it place important institutions related to itself in the sky at a mere height of $36{,}000$ kilometers?

Do you not think magic is an extreme thing? Just thinking can produce heat or mass. This is too ridiculous, beyond human wisdom. Leaving aside god-like beings that surpass human intelligence, how could a tiny life form, a subspecies of humans, the magicians, possibly have such powerful strength?

In other words, a magician is a faucet, and the water source is somewhere else.

The stars are scattered by Superman Machinery, life machines that supply magical power and suppress magic. Besides that, they might be nothing at all.

......

We no longer dream of stars.

Once the principle of how magic is produced is known by the world, it will trigger an apocalyptic war. Now we can only do our best to control information, so that the world will not be interested in this matter.

Problem Description

Given a tree with $n$ nodes, node $i$ has a value $a_i$.

Define the maximal monochromatic connected component containing a node $x$ as a maximal set of nodes $S$ satisfying $x \in S$, and for any $i, j \in S$, there exists a node sequence $p_1, p_2, ... p_t$ such that $p_1 = i$, $p_t = j$, and for every integer $k \in [1, t)$, $p_k$ and $p_{k+1}$ are adjacent in the tree, $a_{p_k} = a_{p_{k+1}}$, and $p_k \in S$.

There are $m$ operations:

1 x y: Given a node $x$, modify the value of every node in the maximal monochromatic connected component containing $x$ to $y$.

2 x: Given a node $x$, query the size of the maximal monochromatic connected component containing $x$.

Input Format

The first line contains two integers $n, m$.

The second line contains $n-1$ integers. The $i$-th integer denotes the parent index of node $i+1$ in the tree, and it is guaranteed that the parent index is smaller than the node index.

The third line contains $n$ integers. The $i$-th integer denotes $a_i$.

Then follow $m$ lines, each in the form 1 x y or 2 x, with meanings as described above.

Output Format

For each operation of type $2$, output one line containing one integer, the answer.

4 5
1 1 2
3 1 1 1
2 4
1 1 1
1 4 3
2 4
1 3 3

2
4

Hint

Idea: nzhtl1477, Solution: nzhtl1477, Code: ccz181078, Data: ccz181078

For $20\%$ of the testdata, $n, m \leq 2\times 10^3$.

For $40\%$ of the testdata, $n, m \leq 2\times 10^5$.

For another $30\%$ of the testdata, $1 \le a_i, y \le 2$.

For $100\%$ of the testdata, $1 \le n, m, a_i, x, y \le 10^6$.

Translated by ChatGPT 5