树上启发式合并（dsu on tree）

· · 个人记录

树上启发式合并用于离线处理一些树上问题，通常是子树询问。

树上启发式合并的本质是链剖分。

算法流程：

第一次 dfs，预处理每个点的父亲、子树大小、重儿子（通常是子树大小最大的儿子），类似树链剖分的第一次 dfs。

第二次 dfs，设当前 dfs 到点 x。首先 dfs x 的所有轻儿子，并将所有点删除。然后 dfs x 的重儿子，并保留所有点。接着将 x 本身及所有轻子树加入。此时 x 子树内所有点都已经被加入。最后处理点 x 的询问。

代码：

const int N=1e5+3;
typedef int ar[N];
ar sn,sz,fa,l,r,p;//l为dfs序编号，r为子树dfs序的编号最大值，p为dfs序编号对应的点编号
int id;
basic_string<int>g[N];
void pre(int x,int y)//第一次dfs
    fa[x]=y,sz[x]=1,p[l[x]=++id]=x;
    for(int i:g[x])if(i!=y)if(pre(i,x),sz[x]+=sz[i],sz[i]>sz[sn[x]])sn[x]=i;
    r[x]=id;
}
void add(int x){}//加入一个点
void del(int x){}//删除一个点
void dfs(int x,bool b){//b=1表示需要删除，否则不需要
    for(int i:g[x])if(i!=fa[x]&&i!=sn[x])dfs(i,1);//dfs轻儿子
    if(sn[x])dfs(sn[x],0);//dfs重儿子
    add(x);//加入点x
    for(int i:g[x])if(i!=fa[x]&&i!=sn[x])for(int j=l[i];j<=r[i];++j)add(p[j]);//加入轻子树
    //处理点x的询问省略
    if(b)for(int i=l[x];i<=r[x];++i)del(p[i]);//删除所有点
}
int main(){
    //读入等部分省略
    pre(1,0),dfs(1,0);
    return 0;
}

时间复杂度：O(n\log n+q)。此处假设加点、删点、回答询问的时间均为 O(1)。

空间复杂度：O(n+q)。

时间复杂度证明：

每个点的某个轻子树大小一定小于这个点的子树大小的一半，所以根结点到任意点的路径上轻边（即父亲到轻儿子的边）不超过 \log n 条，所以每个点属于的轻子树不超过 \log n 个。

dfs 到点 x 时，若 x 是轻儿子，则复杂度为 O(sz_x)；否则为 O(\sum sz_i)，其中 i 为 x 的轻儿子。总复杂度即为 O(\sum sz_x)，其中 x 为轻儿子。因为每个点属于的轻子树不超过 \log n 个，所以总复杂度为 O(n\log n+q)。

在部分题目（如 uoj #284）中，维护的信息和深度有关，可以用长链剖分代替重链剖分，将子树深度最深的儿子作为重儿子，复杂度 O(n)（不含询问）。

总结：

对于一类树上可离线的子树询问问题，若可 O(a\times size) 加入或删除一个子树的贡献，并且可以 O(b) 回答单次询问，则可以用重链剖分 dsu on tree 做到总复杂度 O(an\log n+bq)。

若可以 O(a\times depth) 加入或删除一个子树的贡献，则可以用长链剖分做到 O(an+bq)。

习题：

CF246E Blood Cousins Return

CF600E Lomsat gelral

CF375D Tree and Queries

P4149 [IOI2011]Race

CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

CF715C Digit Tree

uoj #284. 快乐游戏鸡（长链剖分）

P3714 [BJOI2017]树的难题（长链剖分）

参考资料：

OI Wiki 树上启发式合并

CF741D 作者 Arpa 的 blog