TUhjnbcbe - 2025/5/23 17:08:00
树链剖分就是将树分割成多条链，然后利用数据结构（线段树、树状数组等）来维护这些链。别说你不知道什么是树~~╮(─▽─)╭前置知识dfs序LCA线段树……………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………先来回顾两个问题：1，将树从x到y结点最短路径上所有节点的值都加上z这也是个模板题了吧我们很容易想到，树上差分可以以O(n+m)的优秀复杂度解决这个问题2，求树从x到y结点最短路径上所有节点的值之和lca大水题，我们又很容易地想到，dfsO(n)预处理每个节点的dis（即到根节点的最短路径长度）然后对于每个询问，求出x,y两点的lca，利用lca的性质distance(x,y)=dis(x)+dis(y)-2*dis(lca)求出结果时间复杂度O(mlogn+n)现在来思考一个bug：如果刚才的两个问题结合起来，成为一道题的两种操作呢？刚才的方法显然就不够优秀了（每次询问之前要跑dfs更新dis）树剖是通过轻重边剖分将树分割成多条链，然后利用数据结构来维护这些链（本质上是一种优化暴力）首先明确概念：重儿子：父亲节点的所有儿子中子树结点数目最多（size最大）的结点；轻儿子：父亲节点中除了重儿子以外的儿子；重边：父亲结点和重儿子连成的边；轻边：父亲节点和轻儿子连成的边；重链：由多条重边连接而成的路径；轻链：由多条轻边连接而成的路径；比如上面这幅图中，用黑线连接的结点都是重结点，其余均是轻结点，2-11就是重链，2-5就是轻链，用红点标记的就是该结点所在重链的起点，也就是下文提到的top结点，还有每条边的值其实是进行dfs时的执行序号。变量声明：树链剖分的实现1，对于一个点我们首先求出它所在的子树大小,找到它的重儿子（即处理出size,son数组）解释:比如说点1，它有三个儿子2，3，42所在子树的大小是53所在子树的大小是24所在子树的大小是6那么1的重儿子是4ps:如果一个点的多个儿子所在子树大小相等且最大，那随便找一个当做它的重儿子就好了。叶节点没有重儿子，非叶节点有且只有一个重儿子2，在dfs过程中顺便记录其父亲以及深度（即处理出f,d数组），操作1,2可以通过一遍dfs完成dfs跑完大概是这样的，大家可以手动模拟一下3，第二遍dfs，然后连接重链，同时标记每一个节点的dfs序，并且为了用数据结构来维护重链，我们在dfs时保证一条重链上各个节点dfs序连续（即处理出数组top,id,rk）dfs跑完大概是这样的，大家可以手动模拟一下4，两遍dfs就是树链剖分的主要处理，通过dfs我们已经保证一条重链上各个节点dfs序连续，那么可以想到，我们可以通过数据结构（以线段树为例）来维护一条重链的信息回顾上文的那个题目，修改和查询操作原理是类似的，以查询操作为例，其实就是个LCA，不过这里使用了top来进行加速，因为top可以直接跳转到该重链的起始结点，轻链没有起始结点之说，他们的top就是自己。需要注意的是，每次循环只能跳一次，并且让结点深的那个来跳到top的位置，避免两个一起跳从而插肩而过。大家如果明白了树链剖分，也应该有举一反三的能力（反正我没有），修改和LCA就留给大家自己完成了5，树链剖分的时间复杂度树链剖分的两个性质：1，如果(u,v)是一条轻边，那么size(v)size(u)/2；2，从根结点到任意结点的路所经过的轻重链的个数必定都小于logn；可以证明，树链剖分的时间复杂度为\mathcal{O(nlogn)}几道例题：1，树链剖分模板（