如果把根设为1，就没问题。 如果随机一个根，就会在 #4 too short

有大佬能告诉我为啥嘛？

附上代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
const int N=1e5+10,M=6e6+10;
vector<int> e[N];
int dfn[N],sz[N],dep[N],fa[N],son[N],top[N],ts; 
int rt;
int seq[N];
vector<int> nums; 
int w[N];
int n,m,len;
int cnt[N][2];
int ans[M];
bool st[M];
struct node
{
	int id,l,r,t;
	bool operator<(const node &t)const
	{
		int a=l/len,b=t.l/len;
		if(a!=b) return a<b;
		if(a&1) return r<t.r;
		return r>t.r;
	}
}q[M];
int tot;
LL res;
int L=0,R=0;

void dfs1(int u,int p)
{
	fa[u]=p,sz[u]=1,dep[u]=dep[p]+1;
	for(auto v:e[u])
	{
		if(v==p) continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[son[u]]<sz[v]) son[u]=v;
	}
}

void dfs2(int u,int t)
{
	dfn[u]=++ts,seq[dfn[u]]=u,top[u]=t;
	if(son[u]) dfs2(son[u],t);
	for(auto v:e[u])
	{
		if(v==son[u]||v==fa[u]) continue;
		dfs2(v,v);
	}
}

int find(int a,int b)
{
	while(top[a]!=top[b])
	{
		if(fa[top[a]]==b) return top[a];
		a=fa[top[a]];
	}
	return son[b];
} 

void get(int x,vector<PII> &S)
{	
	if(x==rt)
	{
		S.push_back({0,-1});
		S.push_back({n,1});
	} 
	else if(dfn[rt]>dfn[x]&&dfn[rt]<=dfn[x]+sz[x]-1)
	{
		int v=find(rt,x);
		S.push_back({dfn[v]-1,1});
		S.push_back({dfn[v]+sz[v]-1,-1});
		S.push_back({n,1});
	}
	else 
	{
		S.push_back({dfn[x]+sz[x]-1,1});
		S.push_back({dfn[x]-1,-1});
	}
}

void add(int x,int t)
{
	res=(LL)res+cnt[x][t^1];
	cnt[x][t]++;
}

void del(int x,int t)
{
	cnt[x][t]--;
	res=(LL)res-cnt[x][t^1]; 
}

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	len=(double)n/sqrt(m);
	for(int i=1;i<=n;i++) cin>>w[i],nums.push_back(w[i]);
	
	sort(nums.begin(),nums.end());
	nums.erase(unique(nums.begin(),nums.end()),nums.end());
	for(int i=1;i<=n;i++) w[i]=lower_bound(nums.begin(),nums.end(),w[i])-nums.begin()+1;
	
	for(int i=1,a,b;i<n;i++)
	{
		cin>>a>>b;
		e[a].push_back(b),e[b].push_back(a);
	}
	
	rt=1;
	dfs1(rt,0);
	dfs2(rt,rt);
	
	int tot=0;
	for(int i=1,op;i<=m;i++)
	{
		cin>>op;
		if(op==1) 
		{
			int x;
			cin>>x;
			rt=x;
		}
		else
		{
			st[i]=true;
			int x,y;
			cin>>x>>y;
			vector<PII> L,R;
			get(x,L);
			get(y,R);
			for(auto t1:L)
			{	
				int u=t1.first,f1=t1.second;
				for(auto t2:R)
				{
					int v=t2.first,f2=t2.second;
					if(u!=0&&v!=0) q[++tot]={i,u,v,f1*f2};
				}
			}
		}
	}
	
	sort(q+1,q+1+tot);
	for(int i=1;i<=tot;i++)
	{
		int id=q[i].id,l=q[i].l,r=q[i].r,t=q[i].t;
		while(R<r) add(w[seq[++R]],0);
		while(L<l) add(w[seq[++L]],1);
		while(R>r) del(w[seq[R--]],0);
		while(L>l) del(w[seq[L--]],1); 
		ans[id]+=res*t;
	}
	
	for(int i=1;i<=m;i++)
	{
		if(st[i]) cout<<ans[i]<<"\n";
	}
	
	return 0;
}