题目背景

蒟蒻$\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$ 分）：没有任何附加的限制。