自动搬运

查看原文

来自洛谷，原作者为

	shadowice1984 これが勘違いでも、これが勘違いでも

搬运于2025-08-24 22:02:39，当前版本为作者最后更新于2019-01-16 11:11:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

丢人根号分治，打不过拆一堆询问的莫队

这里介绍一种规避莫队的做法

本题题解

给定一颗树，树上每个点有点权，询问x和y的子树当中有多少对点的颜色相等，支持换根

不过我们很快发现换根是假的……，我们用dfs序把这颗树拍平成一个序列

之后我们会发现无论根在哪里，一个点的子树只对应着两种联通块，一种是根为1时的子树，另一个是所有点刨去这个点的一个孩子的子树，这个自行画图理解一下即可，应该不难

那么我们就可以集中精力解决没有换根操作时的问题了

那么我们发现一个非常重要的性质，在这颗树上出现次数大于$\sqrt{N}$的颜色数目不会超过$\sqrt{N}$种

那么意味着我们可以将两种暴力拼在一起，一种是$O(cntm)$的暴力，其中$cnt$是颜色数目，另一种是$O(\sum_{i}cnt(i)^2+m\sqrt{n})$的暴力，其中$cnt(i)$是每一种颜色出现的次数。

那么如果我们对所有出现次数大于$\sqrt{N}$的颜色跑第一种暴力而对所有出现次数小于$\sqrt{N}$的颜色跑第二种暴力的话，我们就可以得到一个复杂度为$O(m\sqrt{n})$优秀做法

所以接下来我们分别介绍两种暴力

case1：当颜色出现次数大于根号n时

恭喜你发现了一道思博题

枚举每个颜色对答案的贡献，令$siz(i)$表示$i$这个子树里有多少个点的颜色是我们枚举的颜色，那么这个颜色对一个询问$(x,y)$的贡献就是$siz(x)siz(y)$

然后我们枚举每一个大于$\sqrt{n}$的颜色跑一遍刚才的暴力就行了，复杂度$O((n+m)\sqrt{n})$

case 2:当颜色的出现次数小于根号n时

恭喜你发现了另一道思博题

此时我们只需要想一个$O(\sum_{i}cnt(i)^2)$的暴力就行了，那么我们可以把所有同色的点对$(x,y)$拉出来

接下来我们观察一下询问，询问的限制是子树，一个子树在dfs序上被映射为了一段区间，那么转化一下询问的要求就是第一个点在一段区间$(l1,r1)$第二个点在另一段区间$(l2,r2)$

这东西似乎是一个矩形询问?

那么这似乎是一个二维数点裸题，询问一个矩形里有多少点……

如果直接拖二维数点的板子离线后跑扫描线的话我们会得到一个丢人的$O(n\sqrt{n}logn+m\sqrt{n})$做法

如果我们调整一下根号分治的上下界的话我们会得到一个$O((n+m)\sqrt{nlogn})$的丢人做法

所以显然不能直接粘二维数点板子，观察到询问只有$O(m)$次，但是修改却有$O(n\sqrt{n})$次，那么这启示我们将树状数组替换为分块，此时我们的复杂度就是$O((n+m)\sqrt{n})$了

实际写的时候你会发现这个数点十分恶心，需要手动拆扫描线才能保证我们询问的次数不是很多……

然后我们就做完这道题~十分好写也不需要卡什么常数就过去了

上代码~

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;const int N=1e5+10;const int BC=230;typedef long long ll;
namespace INPUT_SPACE{
    const int BS=(1<<24)+5;char Buffer[BS],*HD,*TL;
    char gc() { if(HD==TL) TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);return (HD==TL)?EOF:*HD++; }
    inline void read(int& t)
    {
        int x,ch,sgn=1;while(((ch=gc())<'0'||ch>'9')&&ch!='-');
        if(ch=='-') sgn=-1,x=0;else x=ch^'0';
        while((ch=gc())>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^'0');
        t=x*sgn;
    }
}using INPUT_SPACE::read;
const int HB=1<<25;const int TB=(1<<25)-1;
template <typename T>
inline void gm(T* &bas,int siz,T* & op){op=bas;bas=bas+siz+1;}
int dfn[N];int nfd[N];int siz[N];int df;int dg[N];int col[N];int nrt;
struct qry{int u;int v;ll ans;}qr[N*5];int n;int m;int ccnt[N];int bel[N];
inline int isson(int u,int rt){return (nfd[u]<=nfd[rt])&&(nfd[rt]<nfd[u]+siz[u]);}
namespace lsh
{
    map <int,int> mp;
    inline void pre()
    {
        for(int i=1;i<=n;i++)mp[col[i]]=1;map <int,int> :: iterator it,it1;
        for(it=mp.begin(),it1=it,it1++;it1!=mp.end();++it,++it1)it1->second+=it->second;
        for(int i=1;i<=n;i++)col[i]=mp[col[i]];for(int i=1;i<=n;i++)ccnt[col[i]]++;
    }
}
namespace brusolve1
{
    int* v[N];int Eg_bas[N<<2];int* A_t;int csiz[N];int afn[N];int af;
    inline void ih(){A_t=Eg_bas;for(int i=1;i<=n;i++)gm(A_t,dg[i]-(i!=1),v[i]),dg[i]=0;}
    inline void ins(int u,int V){v[u][++dg[u]]=V;}
    inline void pb(int u){afn[++af]=u;}
    inline void calc(int cc)
    {
        for(int i=1;i<=n;i++)csiz[i]=(col[i]==cc);
        for(int i=1;i<=n;i++)
        {int u=afn[i];for(int j=1;j<=dg[u];j++)csiz[u]+=csiz[v[u][j]];}
        for(int i=1,tot=csiz[1];i<=m;i++)
        {
            qry& p=qr[i];
            int c1=(p.u&HB)?tot-csiz[p.u&TB]:csiz[p.u&TB];
            int c2=(p.v&HB)?tot-csiz[p.v&TB]:csiz[p.v&TB];p.ans+=(ll)c1*c2;
        }
    }inline void solve(){for(int i=1;i<=n;i++)if(ccnt[i]>BC)calc(i);}
}
namespace brusolve2
{
    const int B=270;
    struct sqry{int l;int r;int id;};vector <sqry> ve[N];vector <sqry> ed; 
    int* vc[N];int V_bas[N<<2];int* A_t;int a1[N];int sub[N];int bi[N];
    inline int cqry(int l,int r)
    {
        if(bi[l]==bi[r]){int ret=0;for(int i=l;i<=r;i++)ret+=a1[i];return ret;}
        int ret=0;for(int i=l;bi[i]==bi[l];i++)ret+=a1[i];
        for(int i=r;bi[i]==bi[r];i--)ret+=a1[i];
        for(int i=bi[l]+1;i<bi[r];i++)ret+=sub[i];return ret;
    }
    inline void pre()
    {
        A_t=V_bas;for(int i=1;i<=n;i++)
            if(ccnt[i]<=BC){gm(A_t,ccnt[i],vc[i]),ccnt[i]=0;}
        for(int i=1;i<=n;i++)
            {int nc=col[i];if(ccnt[nc]<=BC)vc[nc][++ccnt[nc]]=nfd[i];}
        for(int i=1;i<=n;i++)bi[i]=(i-1)/B+1;
        for(int i=1;i<=m;i++)
        {
            qry& t=qr[i];int tp=(((t.u&HB)>>25)<<1)|((t.v&HB)>>25);
            int u=t.u&TB;int v=t.v&TB;sqry nw=(sqry){nfd[v],nfd[v]+siz[v]-1,0};
            vector <sqry>& q1=ve[nfd[u]-1];vector <sqry>& q2=ve[nfd[u]+siz[u]-1];
            switch(tp)
            {
                case 0:{nw.id=i<<2|1;q1.push_back(nw);nw.id=i<<2|0;q2.push_back(nw);break;}
                case 1:{nw.id=i<<2|3;q1.push_back(nw);nw.id=i<<2|2;q2.push_back(nw);break;}
                case 2:
                {
                    nw.id=i<<2|0;q1.push_back(nw);nw.id=i<<2|1;q2.push_back(nw);
                    ed.push_back((sqry){nfd[v],nfd[v]+siz[v]-1,i<<2|0});break;
                }
                case 3:
                {
                    nw.id=i<<2|2;q1.push_back(nw);nw.id=i<<2|3;q2.push_back(nw);
                    ed.push_back((sqry){nfd[v],nfd[v]+siz[v]-1,i<<2|2});break;
                }
            }
        }
    }
    inline void solve()
    {
        pre();ll tot=0;
        for(int i=1;i<=n;i++)
        {
            int nc=col[dfn[i]];
            if(ccnt[nc]<=BC)for(int j=1;j<=ccnt[nc];j++)
                    a1[vc[nc][j]]++,sub[bi[vc[nc][j]]]++,tot++;
            for(vector <sqry>:: iterator it=ve[i].begin();it!=ve[i].end();++it)
            {
                int ans=cqry(it->l,it->r);ll& tar=qr[it->id>>2].ans;
                switch(it->id&3)
                {
                    case 0:{tar+=ans;break;}case 1:{tar-=ans;break;}
                    case 2:{tar+=tot-ans;break;}case 3:{tar-=tot-ans;break;}
                }
            }
        }for(int i=1;i<=n;i++)a1[i]+=a1[i-1];
        for(vector <sqry>:: iterator it=ed.begin();it!=ed.end();++it)
        {
            int ans=a1[it->r]-a1[it->l-1];ll& tar=qr[it->id>>2].ans;
            if((it->id&3)==0)tar+=ans;else tar+=tot-ans;
        }
    }
}
namespace oldtree
{
    int v[N<<1];int x[N<<1];int ct;int al[N];int fa[N][22];int dep[N];
    inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;dg[u]++;dg[V]++;}
    inline int dfs(int u,int f)
    {
        for(int i=0;fa[u][i];i++)fa[u][i+1]=fa[fa[u][i]][i];
        dfn[++df]=u;nfd[u]=df;
        for(int i=al[u];i;i=x[i])
            if(v[i]!=f)fa[v[i]][0]=u,dep[v[i]]=dep[u]+1,brusolve1::ins(u,v[i]),siz[u]+=dfs(v[i],u);
        brusolve1::pb(u);return ++siz[u];
    }
    inline int cbt(int u,int v)
    {
        int del=dep[v]-dep[u];del--;
        for(int i=0;del;del>>=1,i++)if(del&1)v=fa[v][i];return v;
    }
    inline void build(){brusolve1::ih();dfs(1,0);}
}
int main()
{
    read(n);read(m);
    for(int i=1;i<=n;i++)read(col[i]);lsh::pre();
    for(int i=1,u,v;i<n;i++)read(u),read(v),oldtree::add(u,v),oldtree::add(v,u);nrt=1;
    oldtree::build();
    for(int i=1,tp,u,v;i<=m;i++)
    {
        read(tp);if(tp==1){read(nrt);m--,i--;continue;}
        read(u);read(v);
        if(u==nrt)u=1;else if(isson(u,nrt))u=oldtree::cbt(u,nrt)|(1<<25);
        if(v==nrt)v=1;else if(isson(v,nrt))v=oldtree::cbt(v,nrt)|(1<<25);
        qr[i]=(qry){u,v,0};
    }brusolve1::solve();brusolve2::solve();
    for(int i=1;i<=m;i++)printf("%lld\n",qr[i].ans);return 0;
}