通俗易懂的树链剖分详解

有好多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]软件包管理器


发表于 2019-07-17 10:59:27 in 算法