通俗易懂的树链剖分详解

有好多dalao都有树链剖分的详解，但是他们的文章对本蒟蒻来说都$\large\text{太难啦！！！}$ 所以，这篇文章也就应运而生了。本着为广大的蒟蒻同胞们（~~只有你这么菜啊醒醒~~）的目的，推出了你从未体验过的$\footnotesize\color{green}\text{船新版本}$树链剖分详解，绝对一学就会，一看就懂（但是就算再易懂，请先掌握树的相关知识再来学习，例如：[线段树，一段段的树](https://www.luogu.org/blog/yjpiaomiao/segmenttree)）。 首先，什么是$\footnotesize\color{blue}\text{树链剖分}$？ 树链剖分，计算机术语，指一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结构（树状数组、BST、SPLAY、线段树等）来维护每一条链。（摘自[百度百科](https://baike.baidu.com/item/%E6%A0%91%E9%93%BE%E5%89%96%E5%88%86/10524122?fr=aladdin)） 看不懂？没有关系，接下来将用图示的方法带你学会树链剖分。 这是一张葬爱家族的族谱：  位于顶上的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，标记出每个节点的父亲、深度、子树的节点数，并且找出每个节点的重儿子。 ```cpp 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序，来方便使用数据结构来维护。 ```cpp 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 【模板】树链剖分](https://www.luogu.org/problemnew/show/P3384) [P2486 [SDOI2011]染色](https://www.luogu.org/problemnew/show/P2486) [P2146 [NOI2015]软件包管理器](https://www.luogu.org/problemnew/show/P2146)