通俗易懂的树链剖分详解

· · 个人记录

有好多dalao都有树链剖分的详解，但是他们的文章对本蒟蒻来说都\large\text{太难啦！！！}

所以，这篇文章也就应运而生了。本着为广大的蒟蒻同胞们（只有你这么菜啊醒醒）的目的，推出了你从未体验过的\footnotesize\color{green}\text{船新版本}树链剖分详解，绝对一学就会，一看就懂（但是就算再易懂，请先掌握树的相关知识再来学习，例如：线段树，一段段的树）。

首先，什么是\footnotesize\color{blue}\text{树链剖分}？

树链剖分，计算机术语，指一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结构（树状数组、BST、SPLAY、线段树等）来维护每一条链。（摘自百度百科）

看不懂？没有关系，接下来将用图示的方法带你学会树链剖分。

这是一张葬爱家族的族谱：

位于顶上的1号位的，正是葬爱家族的族长——myt。myt已经很老啦，作为一个快要退役的OIer族长，对于他来说，一个人管理葬爱家族已经十分困难了，于是他决定采用现代化的管理方式，让把家族的事物分成几个部分，让每个父亲选一个最器重的儿子来帮助管理他的事物，其他的儿子则分配其他的事物（明明是古代的分封）。

怎么选择最器重的儿子呢？myt想，以他为首的小家族人数更多的儿子一定更有能力（真是彻头彻尾的封建思想），于是他拿出了族谱，开始搜寻了起来。他给每一个儿子、孙子、曾孙子……都标上了辈分，并且写下了每个子孙的父亲，以及小家族人数。

于是，他选择了4号儿子作为他最器重的儿子，也就是\footnotesize\color{red}\text{重儿子}，连接他们两人的边则是一条\footnotesize\color{red}\text{重边}。

再为4号儿子及其子孙选择他们的重儿子，便构成了一条全是重儿子的关系链，称为\footnotesize\color{red}\text{重链}。

myt剩下的儿子，因为并不重要，在myt心里没有什么重量，也就是\footnotesize\color{red}\text{轻儿子}，由轻儿子之间的边\footnotesize\color{red}\text{轻边}组成关系链也被成为\footnotesize\color{red}\text{轻链}。他们被myt分了一些不重要的职务，只好独立成家。他们又找出了各自的重儿子，构成了几条重链。剩下的轻儿子又自己成家……如此下去，葬爱家族的职务便被明确的分配为了由几条重链构成的结构。

将如葬爱家族族谱般的树型结构划分为多条重链的过程，就是树链剖分。

至于剩下的代码实现，只要理解了过程，就很简单了。

第一次dfs，标记出每个节点的父亲、深度、子树的节点数，并且找出每个节点的重儿子。

void dfs1(int now,int father,int depth)
{
    fa[now]=father; //记录父亲
    dep[now]=depth; //记录辈分（深度）
    size[now]=1; //标记当前的初始小家族（子树）人数（节点数）为1
    for(int i=head[now];i!=0;i=e[i].nxt)
        if(e[i].to!=father)
        {
            dfs1(e[i].to,now,depth+1) //辈分变小（深度变深）
            size[now]+=size[e[i].to];
            if(size[e[i].to]>size[son[now]])
                son[now]=e[i].to; //如果当前的后代数更多，就成为重儿子
        }
    return;
}

第二次dfs，连接重链，并且根据重链标注出dfs序，来方便使用数据结构来维护。

void dfs2(int now,int nowt)
{
    top[now]=nowt; //通过标记当前链的链首来连接重链
    id[now]=cnt++; //记录dfs序
    rk[cnt]=now; //记录dfs序指向的节点
    if(son[now]==0) return;
    dfs2(son[now],nowt); //优先延伸重链，使同一条重链上的dfs序连续
    for(int i=head[now];i!=0;i=e[i].nxt)
        if(e[i].to!=son[now] && fa[now])
            dfs2(e[i].to,e[i].to); //下一条重链的开始
    return;
}

根据树链剖分的两个性质：

1.若(u,v)为一条轻边，size(v)<size(u)\div2

2.从根节点到任意节点的路径经过的轻边数量小于\log n

可以得出，树链剖分的时间复杂度为O\left(n\log^2 2n\right)，显然是一种优秀的算法。

看到这里，相信你已经熟练的掌握树链剖分啦，快去刷几道题练练手吧！

P3384 【模板】树链剖分

P2486 [SDOI2011]染色

P2146 [NOI2015]软件包管理器