Background

Rookie $\color{grey}{\text{suwakow}}$ spent three days and came up with an excellent (but rather nasty) solution for linear space for this problem, which does not rely on randomness in the input. So she decided to use it to torture everyone.

Problem Description

There is a rooted tree with $n$ nodes. The root is node $1$, and node $i$ has color $a_i$. You need to handle $m$ queries of the following two types:

• $1~x~y$: Query how many different colors appear on the shortest path from node $x$ to node $y$ in the tree.

• $2~a~b$: Randomly choose a node $x$ on the path from node $a$ to the root, and randomly choose a node $y$ on the path from node $b$ to the root. Compute the expected value of the answer to query $1~x~y$. (The paths include $a$, $b$, and the root.)

For query type $2$, let the answer be $\mathrm{ans}$. Let $\mathrm{cnt_a}$ be the number of nodes on the path from $a$ to the root, and let $\mathrm{cnt_b}$ be the number of nodes on the path from $b$ to the root. You only need to output $\mathrm{ans}\cdot \mathrm{cnt_a}\cdot \mathrm{cnt_b}$.

Input Format

Note: The input format is different from the original problem.

Each test point contains only one test case.

The first line contains two non-negative integers $n$, $m$, representing the number of nodes and the number of queries.

The next line contains $n$ positive integers. The $i$-th positive integer is $a_i$, representing the color of node $i$.

The next $n-1$ lines each contain two integers $u$, $v$, indicating that there is an edge between node $u$ and node $v$. It is guaranteed that these edges form a tree.

The next $m$ lines each contain one query. The format and meaning of the queries are given in the description.

Output Format

Output $m$ lines. The $i$-th line contains one non-negative integer, representing the answer to the $i$-th query.

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

1
5
1

10 5
3 4 3 8 9 3 2 8 5 7
1 2
2 3
3 4
4 5
5 6
4 7
4 8
8 9
8 10
1 1 10
2 3 5
2 7 5
2 5 4
1 8 6

4
34
61
45
3

Hint

For all data, it is guaranteed that $1\leq a_1, a_2, \ldots, a_n\leq n\leq 10^5$, $1\leq m\leq 2\times 10^5$. It is guaranteed that the input edges form a tree.

Subtask $1$ ($30$ points): There are no type $2$ queries.

Subtask $2$ ($30$ points): For every edge, $v=u+1$.

Subtask $3$ ($40$ points): There are no additional constraints.

Translated by ChatGPT 5