P5669 [SDOI2018] 原题识别-改

蒟蒻$\color{grey}{\text{suwakow}}$花了三天时间，研究出了[这道题](https://www.luogu.org/problem/P4618)的**线性空间**，且不依赖输入的随机性的一种优（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$次询问的答案。

对于所有数据，保证$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$分）：没有任何附加的限制。