1. 前言

如果给你一棵树,求点u到点v路径上点的权值之和,你可能会说:倍增啊!

那如果出题人:我还要你支持修改某个点的权值!

或者再j一点:我还要你支持修改点u到点v路径上点的权值!

那就得用树链剖分了。

2. 什么是树链剖分

上面那个问题,树上区间修改。

区间修改最常见做法就是线段树了。

那我们怎么用线段树维护一颗。。。普通的树呢?

那就给普通的树的每个节点标个号,然后放线段树里呗。区间维护。

但如果随便标号,那点u到点v路径不一定标号是连续的啊,你线段树维护个j啊

所以我们现在引入一个(堆)姿势:



那么这些姿势有什么用呢?先看一道题吧!

传送门= ̄ω ̄=

我们先来看张图:

图中标在边上了,但也不影响我们学。。。

标号方法是:跑dfs,先给当前节点标号,再给重儿子标号(重儿子和当前节点在一个重链上),然后对重儿子递归,最后给剩下的别的儿子标号(别的儿子不和当前节点在一个重链上,所以新建重链,把新建的重链的顶端节点设为那个”别的儿子“)、递归(图中是先给重(zhong)边标号,再给剩下的边标号)。标号从小到大。

不难发现一条重链上的标号是连续的,比如点1到点14,点2到点12

这意味着在线段树中,它们是在一个连续的区间里的,而不是像随便标号时断断续续的。

这样就很好用线段树处理了。

如果两个节点不在一条重链上呢?比如图中的点11和点10,我们要求它们之间的路径上的点权和

那我们就看,点11所在的重链是11->6->2,点10所在的重链是10(10所在的重链只有一个点,就是10)。所以我们就先求出重链11->6->2上的点权和、重链10上的点权和。这两条重链在线段树上都是一段连续的区间,可以直接log2n求出

这时候我们发现还有4->1的重链没有计算,就把它的点权和计算出来,三个重链的点权和加在一起就得到了答案。

所以我们要记录的是:
1. pos[i] 点i的标号
2. top[i] 点i所在重链的顶端节点
3. siz[i] 以点i为根的子树的大小
4. dep[i] 点i的深度
5. fa[i] 点i的父亲节点

我们先跑一边dfs,算出fa、size、dep

然后再跑一边dfs,根据size[i]找出点i的重儿子,然后算出pos、top。

具体代码:

搞完这些就很easy了,因为一段重链在线段树里是一段连续的区间(这是坠重要的)。

我们在查询/修改从点u到点v的路径时,先找到所在重链的顶端节点(top)深度较深的(因为这样能让u和v同步提升,防止一个提到根节点了,另一个还没提,这时候你就不知道提谁了),注意不能按照u和v的深度来提!比如top较深的点是u,然后就用线段树处理区间$[pos[top[u]],pos[u]]$(因为top[u]的标号一定比u要小),再设置u为fa[top[u]],把u往上提,直至u和v在一条重链上(即top[u]==top[v])。这时候可能u和v之间还有一段距离,此时u和v已经在一条重链上,直接处理它们之间的区间就行了。

然后复杂度就是:$O(Nlog_{2} N+Qlog^{2} N)$

同时这个复杂度也是一般的树链剖分的复杂度。因为重链个数不会超过$log_{2} N$个,线段树复杂度是$log_{2} N$的。网上有证明,我就不做过多赘述

代码: