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