P5669 [SDOI2018] Original Problem Recognition - Modified.

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

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}$.

**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 $m$ lines. The $i$-th line contains one non-negative integer, representing the answer to the $i$-th query.

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