分析
以 $1$ 为根 DFS 一次,那么换根后任意子树对应 DFS 序上至多两个区间。
因此对于两棵子树的询问可以拆成 DFS 序上若干对区间的询问。
设 $f(l_1,r_1,l_2,r_2)$ 表示 DFS 序上 $[l_1,r_1]$ 和 $[l_2,r_2]$ 的答案,容斥一下得到
$$ f(l_1,r_1,l_2,r_2)=f(1,r_1,1,r_2)-f(1,l_1-1,1,r_2)-f(1,r_1,1,l_2-1)+f(1,l_1-1,1,l_2-1) $$
这样就可以直接莫队了。
令块大小为 $\frac{n}{\sqrt{m}}$,则莫队的复杂度为 $\mathcal{O}(n\sqrt{m})$。
代码
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;
typedef long long ll;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=100000+10,M=500000+10;
int n,m,Q,rt=1;
int a[N],w[N],S[N];
int B,C,bl[N];
int dep[N],fa[N],sz[N],hson[N],top[N],st[N],ed[N],tim=0;
int cntL[N],cntR[N]; ll now=0,ans[M];
struct query { int l,r,id,w; } q[M*16];
bool operator <(query a,query b) {
return bl[a.l]^bl[b.l]?a.l<b.l:a.r<b.r;
}
struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
static int cnt=0;
e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}
inline void dfs1(int u,int f) {
dep[u]=dep[fa[u]=f]+1,sz[u]=1;
for (re int i=head[u];i;i=e[i].nxt) {
int v=e[i].v; if (v==f) continue;
dfs1(v,u); sz[u]+=sz[v];
if (sz[v]>sz[hson[u]]) hson[u]=v;
}
}
inline void dfs2(int u,int anc) {
top[u]=anc,st[u]=++tim;
if (hson[u]) dfs2(hson[u],anc);
for (re int i=head[u];i;i=e[i].nxt)
if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
ed[u]=tim;
}
inline int getlca(int u,int v) {
while (top[u]^top[v]) {
if (dep[top[u]]<dep[top[v]]) swap(u,v);
u=fa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
inline int jump(int u,int t) {
int v;
while (top[u]^top[t]) v=top[u],u=fa[top[u]];
return u==t?v:hson[t];
}
inline void addquery(int l1,int r1,int l2,int r2,int id) {
q[++Q]=(query){r1,r2,id,1};
if (l1>1) q[++Q]=(query){l1-1,r2,id,-1};
if (l2>1) q[++Q]=(query){r1,l2-1,id,-1};
if (l1>1&&l2>1) q[++Q]=(query){l1-1,l2-1,id,1};
}
inline void addL(int w) { ++cntL[w],now+=cntR[w]; }
inline void delL(int w) { --cntL[w],now-=cntR[w]; }
inline void addR(int w) { ++cntR[w],now+=cntL[w]; }
inline void delR(int w) { --cntR[w],now-=cntL[w]; }
int main() {
n=read(),m=read();
for (re int i=1;i<=n;++i) S[i]=a[i]=read();
sort(S+1,S+n+1); int c=unique(S+1,S+n+1)-S-1;
for (re int i=1;i<=n;++i) a[i]=lower_bound(S+1,S+c+1,a[i])-S;
for (re int i=1;i<n;++i) {
int u=read(),v=read();
addEdge(u,v),addEdge(v,u);
}
dfs1(1,0),dfs2(1,1);
for (re int i=1;i<=n;++i) w[st[i]]=a[i];
for (re int i=1;i<=m;++i) {
int op=read();
if (op==1) { rt=read(),--i,--m; continue; }
int x=read(),y=read();
int lx[3],rx[3],sx=0,ly[3],ry[3],sy=0;
if (x==rt) sx=1,lx[1]=1,rx[1]=n;
else if (getlca(rt,x)!=x) sx=1,lx[1]=st[x],rx[1]=ed[x];
else { int v=jump(rt,x);
if (st[v]>1) ++sx,lx[sx]=1,rx[sx]=st[v]-1;
if (ed[v]<n) ++sx,lx[sx]=ed[v]+1,rx[sx]=n;
}
if (y==rt) sy=1,ly[1]=1,ry[1]=n;
else if (getlca(rt,y)!=y) sy=1,ly[1]=st[y],ry[1]=ed[y];
else { int v=jump(rt,y);
if (st[v]>1) ++sy,ly[sy]=1,ry[sy]=st[v]-1;
if (ed[v]<n) ++sy,ly[sy]=ed[v]+1,ry[sy]=n;
}
for (re int p=1;p<=sx;++p)
for (re int q=1;q<=sy;++q)
addquery(lx[p],rx[p],ly[q],ry[q],i);
}
B=n/sqrt(m);
for (re int i=1;i<=n;++i) bl[i]=(i-1)/B+1;
sort(q+1,q+Q+1);
for (re int i=1,l=0,r=0;i<=Q;++i) {
while (l<q[i].l) ++l,addL(w[l]);
while (l>q[i].l) delL(w[l]),--l;
while (r<q[i].r) ++r,addR(w[r]);
while (r>q[i].r) delR(w[r]),--r;
ans[q[i].id]+=now*q[i].w;
}
for (re int i=1;i<=m;++i) printf("%lld\n",ans[i]);
return 0;
}