Luogu

分析

以 $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;
}