[Ynoi2016]这是我自己的发明

题目背景

一切伟大的世界历史事件与人物,可以说都会出现两次 第一次是作为悲剧出现 第二次,则是作为笑剧出现 ——《路易.波拿巴的雾月十八日》 感动、 痛苦、 以及快乐、 都只是遥不可及的宝石 即便如此,人们啊, 获得幸福吧! ![](https://cdn.luogu.com.cn/upload/pic/21098.png) 世界将在7月20日终结 世界回归天空的日子 万物被天空侵染的日子 回归天空的日子 世界必须回归 世界的极限 世界的尽头 世界的终结 ![](https://cdn.luogu.com.cn/upload/pic/21099.png) 你看…那就是极限…最尽头的天空 如今,已无应该之事了如今,已无忘却之物了 不需要的话语 ![](https://cdn.luogu.com.cn/upload/pic/21100.png) 告别了永不相交的平行,我被吸进了… 垂直下落的世界 ![](https://cdn.luogu.com.cn/upload/pic/21101.png) 虽哭亦喜 虽悲亦喜 各种感情混在一起... 比起其他所有,想必还是高兴占多吧 她高兴地抱着我 紧紧地抱着 再也不会松开了... 想永远这样... 她的思绪,以比语言更快的速度,传达给了我 有些东西,比语言更快 她的思绪,以比语言更快的速度,传达给了我 有些东西,比语音更准确 世界上无论多么短暂的瞬间,都有意义 有意义 块临近终结了 最后的瞬间 啊啊... 远方的警笛声 黑色的天空 月正笑 地正润潮 星正舞 风正凉 在我怀中,温暖的, 橘希实香 ![](https://cdn.luogu.com.cn/upload/pic/21103.png) 她在我的怀中...静静地合上了双眼 然后我也... 静静地合上了双眼

题目描述

您正在打 galgame,然后突然家长进来了,于是您假装在写数据结构题: 给一个树,$n$ 个点,有点权,初始根是 1。 $m$ 个操作,种类如下: `1 x` 将树根换为 $x$。 `2 x y` 给出两个点 $x,y$,从 $x$ 的子树中选每一个点,$y$ 的子树中选每一个点,求点权相等的情况数。

输入输出格式

输入格式


第一行两个数表示 $n,m$。 第二行 $n$ 个数,表示每个点的点权 $a_i$。 之后 $n-1$ 行 , 每行两个数 $x,y$ , 表示一条边。 之后 $m$ 行,每行表示一个操作。

输出格式


对于每个询问,输出一个数表示答案。

输入输出样例

输入样例 #1

5 5
1 2 3 4 5
1 2
1 3
3 4
3 5
2 4 5
2 1 5
2 3 5
1 5
2 4 5

输出样例 #1

0
1
1
1

说明

Idea:nzhtl1477,Solution:nzhtl1477,Code:nzhtl1477,Data:nzhtl1477 【数据范围】 对于 $100\%$ 的数据,$1\le n \le 10^5$,$1 \le m \le 5\times 10^5$ , $1 \le a_i \le 10^9$。