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