RT不知道咋了

// Problem: P4689 [Ynoi2016] 这是我自己的发明
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4689
// Memory Limit: 512 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <stdio.h>
#include <string.h> 
#include <algorithm>
#include <bitset>
#define od(x) printf("%lld",x)
#define odb(x) printf("%lld ",x)
#define odl(x) printf("%lld\n",x)
#define odp(x,y) printf("%d %d\n",x,y)
#define ol(x) puts("")
#define old(x) printf("%lld",x)
#define oldb(x) printf("%lld ",x)
#define oldl(x) printf("%lld\n",x)
#define oldp(x,y) printf("%lld %lld\n",x,y)
#define int long long
inline int read()
{
	int num=0,f=1;char c=getchar();
	while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
	while(c>47&&c<58)num=num*10+(c^48),c=getchar();
	return num*f;
}
inline int re1d()
{
	char c=getchar();
	while(c<48||c>49)c=getchar();
	return c&1;
}
inline int min(int a,int b){return a>b?b:a;}
inline int max(int a,int b){return a<b?b:a;}
const int B=555;
struct querys{
	int l,r,lb,i;
	bool operator<(const querys & b)const{return lb==b.lb?((lb&1)?r<b.r:r>b.r):lb<b.lb;}
}q[2000005];
struct Edge{
	int v,nxt;
}e[1000005];
typedef int arr[2000005];
arr dfn,lst,h,d,res;
int f[400005][20];
int cc,cnt=1;
inline void addedge(int u,int v)
{
	e[cnt]=(Edge){v,h[u]};
	h[u]=cnt++;
}
void dfs(int u,int fa)
{
	dfn[u]=++cc;
	d[u]=d[fa]+1;
	f[u][0]=fa;
	for(int i=1;i<19;i++)f[u][i]=f[f[u][i-1]][i-1];
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v!=fa)dfs(v,u);
	}
	lst[u]=cc;
}
inline void ins(int root,int u,int& l,int& r,int n)
{
	if(root==u)
	{
		l=1,r=n;
		return;
	}
	if(dfn[u]<dfn[root]&&dfn[root]<=lst[u])
	{
		for(int i=18;i>=0;i--)if(d[root]-(1<<i)>d[u])root=f[root][i];
		// [ 1 , dfn[root] - 1 ] U [ lst[root] + 1 , n ]
		l=lst[root]+1,r=dfn[root]-1+n;
	}
	else l=dfn[u],r=lst[u];
}
arr a,b,c1,c2;int ans;
inline void addl(int x){c1[a[x]]++,ans+=c2[a[x]];}
inline void addr(int x){c2[a[x]]++,ans+=c1[a[x]];}
inline void rmvl(int x){c1[a[x]]--,ans-=c2[a[x]];}
inline void rmvr(int x){c2[a[x]]--,ans-=c1[a[x]];}
signed main()
{
	int n=read(),m=read();
	for(int i=1;i<=n;i++)a[i]=b[i]=read();
	std::sort(b+1,b+1+n);
	for(int i=1;i<=n;i++)a[i]=a[i+n]=std::lower_bound(b+1,b+n+1,a[i])-b;
	for(int i=1;i<n;i++){int u=read(),v=read();addedge(u,v);addedge(v,u);}
	dfs(1,0);
	int root=1;
	int cc=0,ccc=0;
	while(m--)
	{
		int op=read();
		if(op==1)root=read();
		else
		{
			int x=read(),y=read();
			int cl,cr,dl,dr;
			ins(root,x,cl,cr,n);
			ins(root,y,dl,dr,n);
			++cc;q[cc]=(querys){cr,dr,cr/B,cc};
			++cc;q[cc]=(querys){cr,dl-1,cr/B,cc};
			++cc;q[cc]=(querys){cl-1,dr,(cl-1)/B,cc};
			++cc;q[cc]=(querys){cl-1,dl-1,(cl-1)/B,cc};
			++ccc;
		}
	}
	std::sort(q+1,q+1+cc);
	int cl=0,cr=0;
	for(int i=1;i<=cc;i++)
	{
		int l=q[i].l,r=q[i].r;
		while(cl<l)addl(++cl);
		while(cr<r)addr(++cr);
		while(cr>r)rmvr(cr--);
		while(cl>l)rmvl(cl--);
		res[q[i].i]=ans;
	}
	for(int i=1;i<=ccc;i++)odl(res[i*4]+res[i*4-3]-res[i*4-1]-res[i*4-2]);
	return 0;
}