Background

All great world-historical facts and characters, so to speak, occur twice.

The first time as tragedy.

The second time as farce.

— The Eighteenth Brumaire of Louis Bonaparte

Moved,

In pain,

And in joy,

Are all just faraway gems.

Even so, people,

Obtain happiness!

The world will end on July 20.

The day the world returns to the sky.

The day everything is stained by the sky.

The day it returns to the sky.

The world must return.

The world’s limit.

The end of the world.

The end of the world.

Look... that is the limit... the sky at the very end.

Now, there is nothing that should be done. Now, there is nothing left to forget.

Words are not needed.

Saying goodbye to the parallel that never intersected, I was sucked into...

A world of vertical falling.

Crying yet joyful.

Sad yet joyful.

All kinds of feelings mixed together...

Compared to everything else, happiness probably takes up more.

She hugged me happily.

Held me tightly.

Never letting go again...

I want it to be like this forever...

Her thoughts reached me faster than words.

Some things are faster than words.

Her thoughts reached me faster than words.

Some things are more accurate than speech.

No matter how brief a moment is in this world, it has meaning.

Meaning.

The block is nearing its end.

The final moment.

Ah...

A distant siren.

A black sky.

The moon is smiling.

The ground is damp.

The stars are dancing.

The wind is cool.

Warm in my arms,

Kishima Kikkou.

In my arms... she quietly closed her eyes.

And then I also...

Quietly closed my eyes.

Problem Description

You are playing a galgame, and then your parents suddenly come in, so you pretend you are solving a data structure problem.

Given a tree with $n$ nodes. Each node has a weight. The initial root is $1$.

There are $m$ operations of the following types:

1 x Change the root of the tree to $x$.

2 x y Given two nodes $x, y$, choose every node from the subtree of $x$ and every node from the subtree of $y$, and count the number of pairs whose node weights are equal.

Input Format

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

The second line contains $n$ integers, where the $i$-th integer is the node weight $a_i$.

The next $n-1$ lines each contain two integers $x, y$, indicating an edge.

The next $m$ lines each describe one operation.

Output Format

For each query, output one integer representing the answer.

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

0
1
1
1

Hint

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

Constraints
For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le m \le 5 \times 10^5$, $1 \le a_i \le 10^9$.

Translated by ChatGPT 5