P4242 树上的毒瘤

Salamander 开心地把一大袋毒瘤带回了家，把他们染上了不同的颜色，并把他们挂在了院子里的树上。

这棵树上有 $n$ 个节点，由 $n-1$ 条树枝相连。初始时树上都挂了一个毒瘤，颜色为 $c_i$。接下来 Salamander 将会进行 $q$ 个操作。 Salamander 有时会修改树上某个点到另外一个点的简单路径上所有毒瘤的颜色。 对于给定的树上**某个点集 $\bm{S}$**，Salamander 还定义了某个点的权值： $$W_i=\sum_{j\in S}T(i,j)$$ 其中 $T(i,j)$ 表示 $i$ 到 $j$ 的路径上毒瘤颜色的**段数**，比如 $i$ 到 $j$ 的路径上毒瘤颜色为 $1223312$ 时，颜色段数为 $5$。 Salamander 对树上的毒瘤们的状态很感兴趣，所以有时会指定树上 $m$ 个节点作为点集，询问这 $m$ 个节点的权值。

第一行包括两个正整数 $n$、$q$，表示树上的节点数和操作个数。 第二行包括用空格隔开的 $n$ 个正整数 $c_i$，表示树上每个节点初始的毒瘤颜色。 接下来 $n-1$ 行，每行两个正整数 $u$、$v$，表示树上有一条连接 $u$ 和 $v$ 的边。 接下来描述 $q$ 个操作： 1. 若给出的第一个整数等于 $1$，那么接下来将会有三个正整数 $u$、$v$、$y$，表示将树上编号为 $u$ 的点到编号为 $v$ 的点的简单路径上的毒瘤颜色全都改为 $y$。 2. 若给出的第一个整数等于 $2$，那么接下来将会有一个正整数 $m$，表示指定的树上节点个数。下一行将会有 $m$ 个用空格隔开的互不相同的正整数，表示当前询问给定的 $m$ 个节点。

若干行，对于每个 $2$ 操作输出对应的答案。

保证输入数据合法。 对于 $30\%$ 的数据，有 $1\leq n,q\leq 1000$，$\sum m\leq 5000$。 对于 $60\%$ 的数据，有 $1\leq n,q\leq 20000$，$\sum m\leq 100000$。 对于 $100\%$ 的数据，有 $1\leq n,q\leq 100000$，$c_i,y\leq 10^9$，$\sum m\leq 200000$，$m\leq n$。