给一个n个点的树，第i个点的值是vi，初始根是1。 有m个操作，每次操作： 1.将树根换为x。 2.给出两个点x，y，求所有点对(a,b)的个数满足a在x子树中，b在y子树中，va==vb
输入描述:
第一行两个数表示n，m第二行n个数，表示每个点的点权vi之后n-1行,每行两个数x,y表示一条边之后m行，每行为：1 x表示把根换成x点2 x y表示查询x点的子树与y点的子树


输出描述:
对于每个询问，输出一行一个数表示答案
示例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

输出

0
1
1
1

备注:
对于100%的数据，1 i = 1e9
加载中...