写点东西记录一下，起码让自己记得自己曾经对树链剖分挺有兴趣:)

首先来看一道题：[BZOJ1036]树的统计

最暴力的做法就是直接修改，然后查询时两个节点往上跳到lca

这样做会很慢，因为它是O(树高)的，随便出个链的数据就能卡掉

所以我们想要每次往上跳很多层，这样跑起来会快一些

也就是顺着“树链”往上跳

我们询问14-10的路径，只需跳(14-12)+[12-9]+(9-1)+(10-3)+[3-1]

树链剖分不是一种具体的算法，而是一种思想

它把整棵树剖分成许多链，并且用数据结构（比如线段树）维护每一条链

于是（往上跳很多层）=（数据结构的区间操作）

既然要顺着链往上跳，我们应该先把树剖分成一些链

常用的方法是"重链剖分"

把一个节点的（子树大小最大的儿子）称为"重儿子"，其余儿子称为"轻儿子"

一个节点向它重儿子连的边称为"重边"，其余边称为"轻边"

如果当前节点为x，边(fa[x],x)为轻边，那么显然size[fa[x]]≥2·size[x]

所以从某个节点向上跳最多经过O(log₂n)条轻边

往上跳的过程中，由于轻边和重链交替出现，所以经过重链的数量级也是O(log₂n)的

挺快的，是吧？

剖分的方法也很简单，两次dfs就可以了

第一次记录深度dep，子树大小siz，重儿子son，父亲fa

第二次记录节点在数据结构中的位置pos，所属重链的顶端bl

dfs完建立数据结构，一般常用线段树或树状数组

查询/修改路径时顺着重链向上跳的同时在数据结构内做区间操作

具体点，查询/修改路径x到y

让dep[bl[x]]≥dep[bl[y]]（深度大的先往上跳）

对区间[pos[bl[x]],pos[x]]操作（这条重链）

让x=fa[bl[x]]（同时跳过一条重链和一条轻边）

重复上述过程直到bl[x]==bl[y]（在同一条重链上）

最后对区间[pos[x],pos[y]]操作（一条重链上的剩余部分）

于是我们就可以愉快地解决路径的问题了w

子树呢？

观察第二个dfs，我们发现一个子树内的节点在数据结构上的位置都是连续的

所以对以x为根的子树操作就直接在数据结构内对[pos[x],pos[x]+siz[x]-1]就可以了

于是我们也可以愉快地解决子树的问题了w

就是这样喵

最后的一点小补充：

因为每次找O(log₂n)条重链

在重链上用数据结构进行操作的时间复杂度是O(log₂n)的

所以......你懂的，树链剖分的总时间复杂度是O(log₂²n)

树链剖分