ZZXYY's blog

树链剖分，用来解决树上路径的统计问题，对树进行DFS，结合线段树等数据结构可以在logN的时间内解决问题。

由于要解决树上的路径问题，而线段树对边建树或者是对点建树都很难将大部分路径上的点或边在一段连续的区间里面，所以我们将树上的路径，或者说链，分为重链和轻链，重链用到的频率高一些，所以我们在建树的时候刻意将在同一条重链上的点或边的编号放在一段连续的区间内，效率就会有所提升。

下面有几个定义，这里直接引用别的地方的：

记siz[v]表示以v为根的子树的节点数，dep[v]表示v的深度(根深度为1)，top[v]表示v所在的重链的顶端节点，fa[v]表示v的父亲，son[v]表示与v在同一重链上的v的儿子节点（姑且称为重儿子），w[v]表示v与其父亲节点的连边（姑且称为v的父边）在线段树中的位置。只要把这些东西求出来，就能用logn的时间完成原问题中的操作。

重儿子：siz[u]为v的子节点中siz值最大的，那么u就是v的重儿子。

轻儿子：v的其它子节点。

重边：点v与其重儿子的连边。

轻边：点v与其轻儿子的连边。

重链：由重边连成的路径。

轻链：由轻边连成的路径。

如何的到上面的各个数据呢？我们可以采用DFS的方式，一般采用的是两次DFS，首先将siz、dep、top、fa、son的值求出，第二次DFS就可以根据已经算出的这些数据弄出重链中点或边的编号。最后按照已有的编号建立线段树或者其他数据结构来解决问题。

但是我们费这么大劲弄出来这些数据有什么用处呢？剖分后的树有着一下的性质：

性质1：如果(v,u)为轻边，则siz[u] * 2 < siz[v]；

这个显然，因为u是v的轻儿子，所以根据重儿子的定义一定存在另一个点k使得siz[k]≥siz[u]，而siz[v]≥siz[k]+siz[u]，从而性质1得证。

性质2：从根到某一点的路径上轻链、重链的个数都不大于logn。

这个要严谨证明是挺麻烦的。。。意会一下吧。。。

有了性质二后，我们对树上两点路径统计时就可以将最坏的时间复杂度降至logN级别，那点小常数就忽略啦，反正也不会有什么影响的。

那么重点来了，有了性质我们还要学会使用他们，具体的修改和查询的办法还是要讲一讲的。

修改和查询比较类似，比如说修改u到v路径上的数据，就先比较他们的top，如果相同就说明他们在同一条重链上，进一步说明在线段树中他们在一段连续的区间内。这时直接上线段树的基本操作就行，如果不在一条重链上，就暴力修改dep较大的那个点或边，然后再从它的父亲和另外一个点继续修改。

最后附上一张效果图：

图例：黑色细边代表轻边，黑色粗边代表重边，黑色数字代表按点建立线段树时节点的编号，蓝色数字代表按边建立线段树时的编号，有红点的节点表示它处在一条重链的顶端。