传送门：here
很棒的莫队题啊.....
题意：
有一棵$ n$个点的树，树上每个点有点权，有$ m$次询问：
操作1：给定两个点$ x,y$，求二元组$ (a,b)$的数量，要求$ a$在$ x$的子树内，$ b$在$ y$的子树内，且$ a$和$ b$的权值相同
操作2：给定点$ x$，将根节点换成$ x$
$ solution:$
我们先考虑没有换根操作
我们先求出这棵树所有点的dfs序，然后可以把树上问题转化成区间询问
$ sumlimits_{i=L1}^{R1}sumlimits_{j=L2}^{R2}[ value[i]=value[j] ]$
会发现这就是LOJ2254
我们令$ g(x,L,R)$表示区间$ [L,R]$中x的数量
则原式等价于$ sumlimits_{x}g(x,L1,R1)g(x,L2,R2)$
化成前缀相减的形式:$ sumlimits_{x}(g(x,1,R1)-g(x,1,L1-1))(g(x,1,R2)-g(x,L2-1,R2))$
令$ f(a,b)=sumlimits_{i=1}^{a}sumlimits_{j=1}^{b}[ value[i]=value[j] ]$
会发现可以化简成$ f(R1,R2)-f(L1-1,R2)-f(R1,L2-1)+f(L1-1,L2-1)$
对于每个$ f(a,b)$，我们记录它的符号以及在第几个询问里，然后可以直接挂在莫队上跑
然后考虑如果有换根操作
我们假定原先的根为$ 1$
然后假设将根换成了$ x$并且询问$ k$的统治区间
我们分三类讨论
$ 1.k=x$
此时子树范围为整个区间
$ 2.k$在$1...x$的路径上
显然$ k$是$ x$的祖先
找出$ k$的孩子中也是$ x$的祖先的节点
设这个节点在以一号点为根时的子树范围为$ [L,R]$
则此时$ k$的统治范围为$ [1,L-1]并上[R+1,n]$
$ 3. othercase $
此时子树和以1为根的子树没有区别
这样我们将每次询问拆成若干区间
然后用上面没有换根的时候的方法扔进莫队暴力计算
可以通过此题
附上我的代码（人菜自带大常数）
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 200010
#define ll long long
using namespace std;
int i,j,k,m,n,x,y,z,cnt,w;ll now;
int up[17][M],F[M],L[M],N[M],a[M],fa[M],size[M],deep[M],v[M],dfn[M],to[M];
int sum[M][2];
inline ll read(){
ll x = 0; char zf = 1; char ch = getchar();
while (ch != '-' && !isdigit(ch)) ch = getchar();
if (ch == '-') zf = -1, ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return x * zf;
}
void write(ll y){if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);}
void writeln(const ll y){write(y);putchar('
');}
inline void ins(const int x,const int p){
now+=sum[x][p^1];
sum[x][p]++;
}
inline void del(const int x,const int p){
now-=sum[x][p^1];
sum[x][p]--;
}
struct query{
int L,R,id,zf,p;
inline bool operator <(const query s)const{
return (p==s.p)?(R<s.R):(p<s.p);
}
}q[4500010];
void add(int x,int y){
a[++k]=y;
if(!F[x])F[x]=k;
else N[L[x]]=k;
L[x]=k;
}
void dfs(int x,int pre){
dfn[x]=++cnt;to[cnt]=x;
up[0][x]=pre;size[x]=1;
for(int i=F[x];i;i=N[i])if(a[i]!=pre){
deep[a[i]]=deep[x]+1;
dfs(a[i],x);
size[x]+=size[a[i]];
}
}
int son(int x,int y){//求出x的孩子中是y的祖先的那个孩子
for(int i=0,s=deep[y]-deep[x]-1;s;i++)if(s>>i&1)s^=(1<<i),y=up[i][y];
return y;
}
bool in(int x,int y){//判断x是否为y的祖先
return dfn[x]<=dfn[y]&&dfn[x]+size[x]-1>=dfn[y];
}
void add(int id,int L1,int R1,int L2,int R2){//将其加入莫队询问
q[++cnt]={R1,R2,id,1,R1/w};
if(L1>1)q[++cnt]={L1-1,R2,id,-1,(L1-1)/w};
if(L2>1)q[++cnt]={R1,L2-1,id,-1,R1/w};
if(L1>1&&L2>1)q[++cnt]={L1-1,L2-1,id,1,(L1-1)/w};
}
struct now{
int L,R;
}aa[3],bb[3];
ll ans[500010];
struct w{
int x,id;
inline bool operator <(const w s)const{
return x<s.x;
}
}c[100010];
int main(){
n=read();m=read();w=300;
for(int i=1;i<=n;i++)c[i].x=read(),c[i].id=i;
sort(c+1,c+n+1);int vv=0;
for(int i=1;i<=n;i++){
if(i==1||c[i].x!=c[i-1].x)vv++;
v[c[i].id]=vv;
}//离散化
for(int i=1;i<n;i++){
x=read();y=read();
add(x,y);
add(y,x);
}
dfs(1,1);cnt=0;
for(int i=1;i<=16;i++)
for(int j=1;j<=n;j++)
up[i][j]=up[i-1][up[i-1][j]];
int nowroot=1,tot=0;
for(int i=1;i<=m;i++){
int opt=read();
if(opt==1){
nowroot=read();
continue;
}
x=read();y=read();tot++;
int cnt1=0,cnt2=0;
if(x==nowroot)aa[++cnt1]={1,n};
else if(in(x,nowroot)){
int pl=son(x,nowroot);
aa[++cnt1]={1,dfn[pl]-1};
aa[++cnt1]={dfn[pl]+size[pl],n};
}
else aa[++cnt1]={dfn[x],dfn[x]+size[x]-1};
if(y==nowroot)bb[++cnt2]={1,n};
else if(in(y,nowroot)){
int pl=son(y,nowroot);
bb[++cnt2]={1,dfn[pl]-1};
bb[++cnt2]={dfn[pl]+size[pl],n};
}
else bb[++cnt2]={dfn[y],dfn[y]+size[y]-1};
//aa和bb存询问点x,y对应的区间
ll ans=0;
for(int q1=1;q1<=cnt1;q1++)
for(int q2=1;q2<=cnt2;q2++)
add(tot,aa[q1].L,aa[q1].R,bb[q2].L,bb[q2].R);//加入询问
}
sort(q+1,q+cnt+1);
int L=0,R=0;now=0;
for(int i=1;i<=cnt;i++){
while(L<q[i].L)ins(v[to[++L]],0);
while(L>q[i].L)del(v[to[L--]],0);
while(R<q[i].R)ins(v[to[++R]],1);
while(R>q[i].R)del(v[to[R--]],1);
ans[q[i].id]+=now*q[i].zf;//莫队计算
}
for(int i=1;i<=tot;i++)writeln(ans[i]);
return 0;
}