P6177题解/树分块学习笔记

· · 题解

没有 Top Cluster 树分块的题解，这里补一发。

定义

考虑将原树划分成 O(\sqrt n) 个大小为 O(\sqrt n) 的树簇，这样对于树上路径问题，就可以像序列问题一样整块整体处理，零散块暴力处理了。

注意，整块整体处理的是簇路径而不是整个树簇。

实现

考虑对原树进行DFS，标记上下界点。

节点 x 为上界点当且仅当：

对于上界点 x，还需要将其子树划分为若干个树簇。考虑将 x 每一个子节点的子树划分到一个树簇中去，那么该过程就非常简单了，即子节点 y 被划分到新的树簇当且仅当：

这个过程略显粗糙，但树簇大小的浮动是在常数级别的，可以接受。

具体实现的时候，只需要在每个上界点打个 tag，然后下传标记即可。

注意，由于上界点一定属于多个树簇，所以一般把上界点 x 归到深度较浅的树簇中（x 在深度较浅的树簇中是下界点），并新建一个上下界点都为 1 的根树簇方便处理。

划分树簇且建收缩树的过程如下：

il void Merge(int x,int y,int i,int ed){
    L[++N]=x,R[N]=y;
    for(;i^ed;i=e1[i].to) 
        if(e1[i].v^fa1[x]) tag[e1[i].v]=N;//标记tag
}
void init1_dfs(int fa,int x){
    int cnt=0;
    fa1[x]=fa,dep1[x]=dep1[fa]+1,res[x]=1;
    for(int i=head1[x];i;i=e1[i].to)
        if(e1[i].v^fa){
            init1_dfs(x,e1[i].v),res[x]+=res[e1[i].v];
            if(Clu[e1[i].v]) cnt++,Clu[x]=Clu[e1[i].v];
        }
    if(cnt>1||res[x]>=B||x==1){
    //若满足三个条件之一,标记上界点,并划分子树
        Clu[x]=x,res[x]=0;
        int sum=1,id=0,li=head1[x];
        for(int i=head1[x];i;i=e1[i].to)
            if(e1[i].v^fa){
                if(sum+res[e1[i].v]>B||(id&&Clu[e1[i].v]))
                    Merge(x,id,li,i),sum=0,id=0,li=i;
                    //划分出新树簇,并更新子树大小,和下界点编号
                if(Clu[e1[i].v]) id=Clu[e1[i].v];
                sum+=res[e1[i].v];
            }
        Merge(x,id,li,0);//最后一部分也要划分成新树簇
    }
}
void down_dfs(int fa,int x,int c=N){
    bl[x]=c;bool fl=0;
    for(int i=head1[x];i;i=e1[i].to)
        if(e1[i].v^fa) fl=1,down_dfs(x,e1[i].v,tag[e1[i].v]?tag[e1[i].v]:c);
    if(!fl&&!R[c]) R[c]=x;
    //如果该树簇没有下界点,就随便选择一个叶节点作下界点
    if(fa1[x]&&!Vis[bl[x]]&&(bl[x]^bl[fa1[x]])){
        Vis[bl[x]]=1;//Vis数组保证 bl[x] 与其父节点不重复连边
        addedge2(bl[x],bl[fa1[x]]);
        addedge2(bl[fa1[x]],bl[x]);
    }
}
void init2_dfs(int fa,int x){
    fa2[x]=fa,dep2[x]=dep2[fa]+1;
    for(int i=head2[x];i;i=e2[i].to)
        if(e2[i].v^fa) init2_dfs(x,e2[i].v);
}
.....
int main(){
    .....
    init1_dfs(0,1),L[++N]=1,R[N]=1,bl[1]=N;
    down_dfs(0,1),init2_dfs(0,N);
    return 0;
}

本题做法

考虑对于本题树分块的做法（以下称树簇为块）。

对于任意两个块 u,v 维护 \{u\rightarrow v\} 路径上所有块簇路径所含颜色的bitset，对于一组询问 x,y，先暴力跑出 x,y 所在块的颜色的bitset，然后再或上两点路径的bitset即可（实际实现可能有些不同）。

对于零散块部分，显然时间复杂度是 O(\sqrt n)，对于整块部分，只需要进行一次合并，所以时间复杂度是 O(\frac{n}{w})。对于预处理部分，分别以每个块为 u 遍历大小为 O(\sqrt n)划分树，时间复杂度 O(\sqrt n \frac{n}{w})，由于有 O(\sqrt n) 个块，所以预处理总时间复杂度为 O(\frac{n^2}{w})。 。

所以该算法的时间复杂度为 O(\frac{n^2}{w}+n\sqrt n)。显然在极限数据下后一部分复杂度小于前一部分，所以可以通过调大块长来优化空间（因为要存两两块之间的bitset，所以空间是 O(\frac{B^2}{w})）。

完整代码如下：

#include<bits/stdc++.h>
#define ull unsigned long long
#define il inline
using namespace std;
const int w=(1<<16)-1;
const int maxn=40010;
const int maxqn=310;
const ull S=18446744073709551615ull;
il int read(){
    int x=0;
    char c=getchar();
    for(;!(c>='0'&&c<='9');c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=(x<<1)+(x<<3)+c-'0';
    return x;
}
struct Hsh{
    int id,x;
    bool operator <(Hsh a)const{return x<a.x;}
}b[maxn];
int nn,pc[1<<16];

//////////bitset
struct Bitset{
    ull a[maxn/64+2];
    il Bitset operator |(Bitset x)const{for(int i=0;i<=nn;i++) x.a[i]|=a[i];return x;}
    il int Count(int cnt=0)const{
        for(int i=0;i<=nn;i++)
            cnt+=pc[a[i]&w]+pc[(a[i]>>16)&w]+pc[(a[i]>>32)&w]+pc[(a[i]>>48)&w];
        return cnt;
    }
}col[maxqn],data[maxqn][maxqn];
il void Add(Bitset &x,int i){x.a[i-1>>6]|=(1ull<<(i-1&63));}
il void clear(Bitset &x){for(int i=0;i<=nn;i++)x.a[i]=0;}
/////////////

struct edge{
    int v,to;
}e1[maxn<<1],e2[maxqn<<1];
int head1[maxn],head2[maxqn];
int ecnt1=1,ecnt2=1;
il void addedge1(int u,int v){
    e1[++ecnt1].v=v,e1[ecnt1].to=head1[u],head1[u]=ecnt1;
}
il void addedge2(int u,int v){
    e2[++ecnt2].v=v,e2[ecnt2].to=head2[u],head2[u]=ecnt2;
}
int a[maxn],n,m,B,N;
int fa1[maxn],dep1[maxn];
int res[maxn],tag[maxn],Clu[maxn];

bool Vis[maxqn];
int fa2[maxqn],dep2[maxqn];
int L[maxqn],R[maxqn];
int bl[maxn];

///////////划分树簇
il void Merge(int x,int y,int i,int ed){
    L[++N]=x,R[N]=y;
    for(;i^ed;i=e1[i].to) 
        if(e1[i].v^fa1[x]) tag[e1[i].v]=N;
}
void init1_dfs(int fa,int x){
    int cnt=0;
    fa1[x]=fa,dep1[x]=dep1[fa]+1,res[x]=1;
    for(int i=head1[x];i;i=e1[i].to)
        if(e1[i].v^fa){
            init1_dfs(x,e1[i].v),res[x]+=res[e1[i].v];
            if(Clu[e1[i].v]) cnt++,Clu[x]=Clu[e1[i].v];
        }
    if(cnt>1||res[x]>=B||x==1){
        Clu[x]=x,res[x]=0;
        int sum=1,id=0,li=head1[x];
        for(int i=head1[x];i;i=e1[i].to)
            if(e1[i].v^fa){
                if(sum+res[e1[i].v]>B||(id&&Clu[e1[i].v]))
                    Merge(x,id,li,i),sum=0,id=0,li=i;
                if(Clu[e1[i].v]) id=Clu[e1[i].v];
                sum+=res[e1[i].v];
            }
        Merge(x,id,li,0);
    }
}
void down_dfs(int fa,int x,int c=N){
    bl[x]=c;bool fl=0;
    for(int i=head1[x];i;i=e1[i].to)
        if(e1[i].v^fa) fl=1,down_dfs(x,e1[i].v,tag[e1[i].v]?tag[e1[i].v]:c);
    if(!fl&&!R[c]) R[c]=x;
    if(fa1[x]&&!Vis[bl[x]]&&(bl[x]^bl[fa1[x]])){
        Vis[bl[x]]=1;
        addedge2(bl[x],bl[fa1[x]]);
        addedge2(bl[fa1[x]],bl[x]);
    }
}
void init2_dfs(int fa,int x){
    fa2[x]=fa,dep2[x]=dep2[fa]+1;
    for(int i=head2[x];i;i=e2[i].to)
        if(e2[i].v^fa) init2_dfs(x,e2[i].v);
}
////////////

//////预处理两两块之间的bitset
void initd_dfs(int rt,int fa,int x,Bitset t){
    t=t|col[x],data[rt][x]=t;
    for(int i=head2[x];i;i=e2[i].to)
        if(e2[i].v^fa) initd_dfs(rt,x,e2[i].v,t);
}
//////////

///////零散块内的暴力
il Bitset Query(int x,int y){
    Bitset ans;clear(ans);
    if(dep1[x]<dep1[y]) swap(x,y);
    while(dep1[x]>dep1[y]) Add(ans,a[x]),x=fa1[x];
    while(x^y){
        Add(ans,a[x]),x=fa1[x];
        Add(ans,a[y]),y=fa1[y];
    }Add(ans,a[x]);
    return ans;
}
////////////

il int Solve(int x,int y){
    Bitset ans;clear(ans);
    int u=bl[x],v=bl[y];
    if(dep2[u]<dep2[v]) swap(u,v),swap(x,y);
    if(u==v) return Query(x,y).Count();
    ans=Query(x,L[u]),u=fa2[u];
    int uu=u;
    while(dep2[uu]-1>dep2[v]) uu=fa2[uu];
    if(dep2[uu]-1==dep2[v])ans=ans|data[u][uu],u=fa2[uu];
    if(u^v){
        ans=ans|Query(y,L[v]),v=fa2[v];
        if(dep2[u]>dep2[v]) ans=ans|col[u],u=fa2[u];
    }
    else return (ans|Query(R[v],y)).Count();
    if(u==v) return ans.Count(); 
    int u_=u,v_=v;
    //注意,lca(u,v) 对应的块实际上是没有走过簇路径的
    //所以需要分别或上 u,v 两侧路径的bitset
    while(fa2[u_]^fa2[v_]) u_=fa2[u_],v_=fa2[v_];
    return (ans|data[u][u_]|data[v][v_]).Count();
}
int main(){
    n=read(),m=read(),B=1000;
    for(int i=1;i<=n;i++){
        a[i]=read();
        b[i]=Hsh{i,a[i]};
    }
    sort(b+1,b+1+n);int val=0;
    b[0].x=-1;
    for(int i=1;i<=n;i++){
        if(b[i].x^b[i-1].x) val++;
        a[b[i].id]=val;
    }nn=val/64;
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        addedge1(x,y),addedge1(y,x);
    }
    for(int i=1;i<(1<<16);i++) pc[i]=pc[i>>1]+(i&1);
    init1_dfs(0,1),L[++N]=1,R[N]=1,bl[1]=N;
    down_dfs(0,1),init2_dfs(0,N);
    for(int i=1;i<=N;i++){
        int x=R[i];Add(col[i],a[x]);
        while(x^L[i]) x=fa1[x],Add(col[i],a[x]);
        //处理每个块簇路径对应的bitset
    }Bitset t;clear(t);
    for(int i=1;i<=N;i++)
        initd_dfs(i,0,i,t);
    int x,y,lans=0;
    while(m--){
        x=read()^lans,y=read();
        printf("%d\n",lans=Solve(x,y));
    }
    return 0;
}

Top Cluster 树分块的优劣