样例输出：

0
0
0
-1

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+5;
int n,m,p,q,B,idx,rt=1,l,r,s,a[N],lsh[N],dfn[N],lst[N],f[N][20],blk[N],pl[N],pr[N],ans[N<<3];
vector<int>g[N];
struct node{int u,tp;};
struct query
{
	int l,r,id,wt;
	bool operator<(query a)
	{
		if(blk[l]^blk[a.l])return blk[l]<blk[a.l];
		if(blk[l]&1)return r<a.r;
		return r>a.r;
	}
}que[N<<7];
void dfs(int u,int fa)
{
	f[u][0]=fa;dfn[u]=++idx;
	for(int i=1;i<20;i++)f[u][i]=f[f[u][i-1]][i-1];
	for(int v:g[u])if(v!=fa)dfs(v,u);
	lst[u]=idx;
}
node get(int u,int v)
{
	if(u==v)return (node){1,0};
	if(dfn[v]<dfn[u]||dfn[v]>lst[u])return (node){u,0};
	for(int i=19;~i;i--)if(dfn[f[v][i]]>dfn[u])v=f[v][i];
	return (node){v,1};
}
void add(node x,node y,int id)
{
	pair<int,int>a[2],b[2];
	if(x.tp)
	{
		a[0]=make_pair(1,dfn[x.u]-1);
		a[1]=make_pair(lst[x.u]+1,n);
	}
	else a[0]=make_pair(dfn[x.u],lst[x.u]);
	if(y.tp)
	{
		b[0]=make_pair(1,dfn[y.u]-1);
		b[1]=make_pair(lst[y.u]+1,n);
	}
	else b[0]=make_pair(dfn[y.u],lst[y.u]);
	for(int i=0,l1,r1,l2,r2;i<=x.tp;i++)for(int j=0;j<=x.tp;j++)
	{
		l1=a[i].first-1;r1=a[i].second;
		l2=b[j].first-1;r2=b[j].second;
		if(r1&&r2)que[++q]=(query){r1,r2,id, 1};
		if(l1&&r2)que[++q]=(query){l1,r2,id,-1};
		if(r1&&l2)que[++q]=(query){r1,l2,id,-1};
		if(l1&&l2)que[++q]=(query){l1,l2,id, 1};
	}
}
void addl(int u)
{
	int w=a[dfn[u]];
	pl[w]++;s+=pr[w];
}
void addr(int u)
{
	int w=a[dfn[u]];
	pr[w]++;s+=pl[w];
}
void dell(int u)
{
	int w=a[dfn[u]];
	pl[w]--;s-=pr[w];
}
void delr(int u)
{
	int w=a[dfn[u]];
	pr[w]--;s-=pl[w];
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){cin>>a[i];lsh[i]=a[i];}
	sort(lsh+1,lsh+n+1);q=unique(lsh+1,lsh+n+1)-lsh-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+q+1,a[i])-lsh;
	for(int i=1,u,v;i<n;i++)
	{
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);q=0;
	for(int i=1,op,u,v;i<=m;i++)
	{
		cin>>op;
		if(op==1)cin>>rt;
		else
		{
			cin>>u>>v;
			add(get(u,rt),get(v,rt),++p);
		}
	}
	B=n/sqrt(q);
	for(int i=1;i<=n;i++)blk[i]=(i-1)/B+1;
	sort(que+1,que+q+1);
	for(int i=1;i<=q;i++)
	{
		cout<<que[i].l<<' '<<que[i].r<<'\n';
		while(que[i].l<l)addl(--l);
		while(que[i].r>r)addr(++r);
		while(que[i].l>l)dell(l++);
		while(que[i].r<r)delr(r--);
		ans[que[i].id]+=s*que[i].wt;
	}
	for(int i=1;i<=p;i++)cout<<ans[i]<<'\n'; 
}