以前没有接触过树链剖分的同学们看到这个东西是不是觉得很高大上呢，下面我将带你们进入树的世界（讲得不好别打我）
首先我们来看一道题
NOI2015D2T2软件包管理器
题目描述如下
Linux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu使用的apt-get，Fedora/CentOS使用的yum，以及OSX下可用的homebrew都是优秀的软件包管理器。
你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包A依赖软件包B，那么安装软件包A以前，必须先安装软件包B。同时，如果想要卸载软件包B，则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除0号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而0号软件包不依赖任何一个软件包。依赖关系不存在环（若有m(m≥2)个软件包A1,A2,A3,?,Am，其中A1依赖A2，A2依赖A3，A3依赖A4，……，A[m-1]依赖Am，而Am依赖A1，则称这m个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。
现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为0。
这道题的大意就是物品之间存在依赖与被依赖的关系，且不构成环，有一个物品无依赖物品。
我们定义一个物品及它所依赖的物品以及依赖的依赖等等为依赖链，依赖链包括这个物品的物品的集合为依赖子树。
那么放一个物品的同时需要放完整的依赖链，拿走一个物品的时候，也需要拿走完整的依赖子树。
通过以上的分析，我们可以看出这大概是一个树形结构。
由于节点个数和操作次数的范围为\(1e5\),明显要用一个\(nlgn\)或者\(nlg^2n\)的算法，那么就可以引出我们今天的主角——树剖了。
顾名思义，树链剖分就是指将一颗树分成若干条链，使得可以使用数据结构（例如线段树，主席树）来进行维护
它的特点很明显，我们可以非常便捷的处理同一条链上的若干点和边
直说上面大概会让大家一头雾水，这只是让大家对树剖有一个初步的概念，下面我们要开始正式的讲解了
先下若干定义
重儿子：子树最大的儿子
轻儿子：除了重儿子以外的所有儿子
重边：父节点与重儿子组成的边
轻边：除重边以外的边
重链：重边连接而成的链
轻链：轻边连接而成的链
下图为例
原文：https://www.cnblogs.com/hanruyun/p/9577500.html