Background

A novice named $\color{grey}{\text{suwakow}}$ spent three days developing an linear space optimized (and somewhat toxic) approach for this problem, which does not rely on the randomness of the input. She decided to share this challenging method with everyone.

Problem Description

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

• $1~x~y$: Query the number of distinct colors on the shortest path from node $x$ to node $y$ in the tree.

• $2~a~b$: Randomly select a point $x$ from the path from node $a$ to the root, and a point $y$ from the path from node $b$ to the root. Find the expected answer for query $1~x~y$ (the paths include nodes $a$, $b$, and the root).

For query $2$, let the answer be $\mathrm{ans}$, the number of points on the path from $a$ to the root be $\mathrm{cnt_a}$, and the number of points on the path from $b$ to the root be $\mathrm{cnt_b}$. 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 case contains only one set of data.

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

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

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

The next $m$ lines each contain a query. The format and meaning of the queries are as described in the problem statement.

Output Format

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

Sample Input and Output

Input Sample #1

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

Output Sample #1

1
5
1

Input Sample #2

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

Output Sample #2

4
34
61
45
3

Notes

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 also guaranteed that the input edges form a tree.

Subtask $1$ ($30$ points): No query of type $2$ exists.

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

Subtask $3$ ($40$ points): No additional restrictions.

见题面 Input 部分

见题面 Output 部分