题目背景

蒟蒻$\color{grey}{\text{suwakow}}$花了三天时间，研究出了这道题的线性空间，且不依赖输入的随机性的一种优（du）秀（liu）做法。于是她决定拿出来毒瘤一下大家。

题目描述

有一棵$n$个点的有根树，根节点编号为$1$，且编号为$i$的节点有颜色$a_i$。你需要支持$m$次询问。询问有以下两种格式：

• $1~x~y$：询问树上编号为$x$的节点到编号为$y$的节点的最短路径中，不同的颜色有多少种。

• $2~a~b$：在节点$a$到根节点的路径中随机选择一个点$x$，在节点$b$到根节点的路径中随机选择一个点$y$，求询问 $1~x~y$ 的答案期望。（路径包含$a$, $b$和根节点）

对于询问$2$，设答案为$\mathrm{ans}$，$a$到根节点的路径经过的点数为$\mathrm{cnt_a}$，$b$到根节点的路径经过的点数为$\mathrm{cnt_b}$，你只需要输出$\mathrm{ans}\cdot \mathrm{cnt_a}\cdot \mathrm{cnt_b}$。

输入格式

注意：输入格式与原题不同

每个测试点仅包含一组数据。

输入数据的第一行包含两个非负整数$n$, $m$，表示节点个数和询问次数。

接下来一行包含$n$个正整数，第$i$个正整数为$a_i$，表示节点$i$的颜色。

接下来$n-1$行，每行包含两个整数$u$, $v$，表示编号为$u$的节点和编号为$v$的节点之间存在一条边。保证输入的边构成一棵树。

接下来$m$行，每行包含一个询问。询问的格式和意义见题目描述。

输出格式

输出$m$行，第$i$行包含一个非负整数，表示第$i$次询问的答案。

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

提示

对于所有数据，保证$1\leq a_1, a_2, \ldots, a_n\leq n\leq 10^5$, $1\leq m\leq 2\times 10^5$。保证输入的边构成一棵树。

子任务$1$（$30$分）：保证不存在询问$2$。

子任务$2$（$30$分）：保证对于每一条边都有$v=u+1$。

子任务$3$（$40$分）：没有任何附加的限制。