别样的树分治——重链分治

· · 算法·理论

树重链分治

引入

在模拟赛中遇到了一道树上问题，经题意转化后需要解决查询树上距离为 d 的点对数量。显然用点分治很容易做，但是出题人几乎将用这种做法的所有人卡掉了，原因是点分治常数太大了。

我们考虑点分治为什么效率低，原因是每轮只取出一个点取出后删掉，但如果我们一次取出一整条链上的点那就不一样了。

为了维持点分治的复杂度，我们每次挑选从根开始的一条重链，由于重心一定在重链上，所以复杂度不会劣于普通点分治。

流程

以 k 距点对计数为例：

  1. 对于当前连通块 U，找出当前连通块所对应的一条从根到叶子的重链 D_U。
  2. 我们按从上到下的顺序遍历这条链，获取链头到当前节点 u 的路径长度 pre_u ，查询桶中 k-pre_u 的数量，将 pre_u 加入桶。
  3. 遍历 u 不在链上的儿子 v，进入 v 的子树，获取对于子树节点 x 到 u 的距离 d_u ，查询桶中 =k-d_x-pre_u 的数量。
  4. 将 v 子树内所有点的 d_x+pre_u 加入桶。
  5. 按此流程处理完整条链，并删除链上的所有节点，向子结点递归。

代码示例

bool del[N];
int sz[N],hs[N],pre[N];
void dfs(int u,int last){
    sz[u]=1;hs[u]=0;
    for(auto i:g[u]){
        if(i==last||del[i])continue;
        dfs(i,u);
        if(sz[i]>sz[hs[u]])hs[u]=i;
        sz[u]+=sz[i];
    }
}
int t[N<<1],mem[N],ed;

ll ans=0;
void getval(int u,int last){
    pre[u]=pre[last]+(u<=n);
    if(u<=n){
        ans+=t[L-pre[u]+N];
        mem[++ed]=u;
    }
    for(auto i:g[u])if(i!=last&&!del[i])getval(i,u);
}

void solve(int u){
    dfs(u,0);
    for(int i=u;i;i=hs[i])del[i]=1;
    int fa=0;
    for(int i=u;i;i=hs[i]){
        pre[i]=pre[fa]+(i<=n);
        if(i<=n){
            ans+=t[L-pre[i]+N];
            t[N-pre[fa]]++;
        }
        for(auto v:g[i]){
            if(del[v])continue;
            ed=0;
            getval(v,i);
            for(int j=1;j<=ed;j++){
                int x=mem[j];
                t[pre[x]-pre[i]-pre[fa]+N]++;
            }
        }
        fa=i;
    }
    for(int i=N-sz[u];i<=N+sz[u];i++)t[i]=0;
    for(int i=u;i;i=hs[i]){
        for(auto j:g[i]){
            if(!del[j])solve(j);
        }
    }
}

进一步分析

回顾流程我们发现实际上链分治的流程包含了点分治，意味着链分治往往不如点分治灵活好写，仅用于优化时间。

实际上我们无需将这个过程类似点分治动态找重心，可以在一开始就进行重链剖分，其余步骤不变，这样我们便可以发现三条性质：

  1. 整个分治的层数虽然也是对数级别，但是常数几乎等于跳重链的时间常数，这是极其优秀的时间了。
  2. 链分治也可以改写为类似于点分树的动态结构，当我们修改一个点时只需要向上跳重链并更新沿途的重链即可，但考虑到链上部分的更新较为复杂（例如用线段树维护链上最大子段和等查询）并且实现相比静态较为困难，表现往往不如普通点分树。
  3. 动态链分治支持路径的修改与查询，常规的树链剖分就是一种动态链分治。

后记

重链分治是作者在训练中无意发现的一种算法，可能有前人提出过也有可能较为 useless，但是由于链分治可以有效针对常规卡点分治的数据点（例如树高较高，每层节点少），在紧急情况下或有妙用（？。