用dfs序把询问表示成询问dfs序的两个区间中的信息
拆成至多9个询问（询问dfs序的两个前缀），对这些询问用莫队处理，时间复杂度$O(n\sqrt{m})$
#include<bits/stdc++.h>
typedef long long i64;
const int N=1e5+;
char buf[N],*ptr=buf+,ob[N],*op=ob;
int G(){
if(ptr-buf==)fread(ptr=buf,,,stdin);
return *ptr++;
}
int _(){
int x=;
if(ptr-buf<){
while(*ptr<)++ptr;
while(*ptr>)x=x*+*ptr++-;
}else{
int c=G();
while(c<)c=G();
while(c>)x=x*+c-,c=G();
}
return x;
}
#define fl fwrite(ob,1,op-ob,stdout),op=ob
void pr(i64 x){
if(op-ob>)fl;
int ss[],sp=;
if(!x)*op++=;
while(x)ss[++sp]=x%,x/=;
while(sp)*op++=ss[sp--]+;
*op++=;
}
i64 ans[N*];
int n,m,rt=;
int v[N],vs[N],qc=;
int es[N*],enx[N*],e0[N],ep=;
int fa[N],sz[N],son[N],dep[N],top[N],id[N][],vi[N],idp=;
void f1(int w,int pa){
dep[w]=dep[fa[w]=pa]+;
sz[w]=;
for(int i=e0[w];i;i=enx[i]){
int u=es[i];
if(u==pa)continue;
f1(u,w);
sz[w]+=sz[u];
if(sz[u]>sz[son[w]])son[w]=u;
}
}
void f2(int w,int tp){
id[w][]=++idp;
vi[idp]=v[w];
top[w]=tp;
if(son[w])f2(son[w],tp);
for(int i=e0[w];i;i=enx[i]){
int u=es[i];
if(u!=fa[w]&&u!=son[w])f2(u,u);
}
id[w][]=idp;
}
int up(int x,int y){
int a=top[x],b=top[y];
while(a!=b){
x=fa[a];
if(x==y)return a;
a=top[x];
}
return son[y];
}
bool chk(int w){
return id[w][]<id[rt][]&&id[rt][]<=id[w][];
}
int pos[N],B,qp=;
struct Q{
int l,r,sgn,id;
}qs[N*],qs1[N*],*ls[N],*lp;
int tr[N],tb[N];
i64 s0[N],_ans;
int ts[N][];
inline void inc0(int x){++ts[x][],_ans+=ts[x][];}
inline void dec0(int x){--ts[x][],_ans-=ts[x][];}
inline void inc1(int x){++ts[x][],_ans+=ts[x][];}
inline void dec1(int x){--ts[x][],_ans-=ts[x][];}
void cal(int w,int*a,int&p){
if(w==rt)a[]=n,p=;
else if(id[w][]<id[rt][]&&id[rt][]<=id[w][]){
w=up(rt,w);
a[]=n;
a[]=-id[w][];
a[]=id[w][]-;
p=;
}else{
a[]=id[w][];
a[]=-id[w][];
p=;
}
}
void ins(int a,int b,int id){
if(!(a&&b))return;
int c=;
if(a<)a=-a,c=-c;
if(b<)b=-b,c=-c;
if(a>b)std::swap(a,b);
if(b==n)ans[id]+=c*s0[a];
else qs[qp++]=(Q){a,b,c,id};
}
int main(){
n=_();m=_();
for(int i=;i<=n;++i)v[i]=vs[i]=_();
std::sort(vs+,vs+n+);
for(int i=;i<=n;++i)v[i]=std::lower_bound(vs+,vs+n+,v[i])-vs;
for(int i=,a,b;i<n;++i){
a=_(),b=_();
es[ep]=b;enx[ep]=e0[a];e0[a]=ep++;
es[ep]=a;enx[ep]=e0[b];e0[b]=ep++;
}
f1(,);
f2(,);
for(int i=;i<=n;++i)inc0(vi[i]);
for(int i=;i<=n;++i)inc1(vi[i]),s0[i]=_ans;
_ans=;
memset(ts,,sizeof(ts));
for(int i=;i<=m;++i){
if(_()==)rt=_();
else{
++qc;
int x=_(),y=_();
int xv[],xp,yv[],yp;
cal(x,xv,xp);
cal(y,yv,yp);
for(int a=;a<xp;++a)
for(int b=;b<yp;++b)ins(xv[a],yv[b],qc);
}
}
B=n/sqrt(qp+)*+;
for(int i=;i<=n;++i)pos[i]=i/B; for(int i=;i<qp;++i)++tr[qs[i].r],++tb[pos[qs[i].l]];
lp=qs1;
for(int i=;i<=n;++i)ls[i]=lp,lp+=tr[i];
for(int i=;i<qp;++i)*ls[qs[i].r]++=qs[i];
lp=qs;
for(int i=;i<=pos[n];++i)ls[i]=lp,lp+=tb[i];
for(int i=;i<qp;++i)*ls[pos[qs1[i].l]]++=qs1[i];
for(int i=;i<pos[n];i+=)std::reverse(ls[i],ls[i+]); int L=,R=;
for(int i=;i<qp;++i){
int l=qs[i].l,r=qs[i].r;
while(L<l)inc0(vi[++L]);
while(L>l)dec0(vi[L--]);
while(R<r)inc1(vi[++R]);
while(R>r)dec1(vi[R--]);
ans[qs[i].id]+=qs[i].sgn*_ans;
}
for(int i=;i<=qc;++i)pr(ans[i]);
return fl,;
}