一般来讲，我们很熟悉序列的操作，对于树上路径的操作会觉得比较棘手。而树链剖分基本思想，是将树上的路径问题转化为序列操作问题。

树链剖分，简单来讲即将一棵树划分为若干条链，然后用数据结构去维护每一条链。

常见的树链剖分方法为轻/重划分。

相关概念

1.对于一棵树，假设size(u)代表以u为根的子树上的节点个数，u的儿子节点为v1,v2,…假设其中size(vi)是其中最大的，我们称vi为u的重儿子，其余vj为u的轻儿子。

2.那么u和vi相连的边为重边，u和其余儿子节点相连的边为轻边。

3.由重边链接起来的路径为重链（一个点也算一条重链），由轻边链接起来的路径为轻链。

如下图，重边黑色显示，其余边为轻边。1-2-5-7为重链，1-3,2-4为轻链。

图1

相关性质

1.如果(u,v)为轻边，则size(v)<=size(u)/2.

证明：反证法，如果size(v)>size(u)/2，那么v应该为重儿子，(u,v)应该为重边。

2.从根到某一点v的路径上的轻边条数不多于O(logn).

证明：首先，到达某个叶子节点经过的轻边数量应该是最多的，由性质1可知，路径上每经过一条轻边(u,v)，u子树上的节点就减少一半。

3.每个点到根上的路径都有不超过logn条轻边和logn条（重链）重路径。

证明：根据性质2，每个点到根的路径一定不会有超过logn条轻边，观察图可以发现，每一条轻边的两个端点一定包含在某两条重链之中，那么重链数量也在logn级别。

轻/重链划分的作用体现？

如果我们对这棵树进行dfs，优先访问每个节点的重儿子，并按照每个节点的发现时间为其盖上时间戳。如下图：

图2

我们可以观察到两个特征：

（1）一条重链上的节点其时间戳是连续的。例如重链1-2-5-7时间戳是1,2,3,4

（2）一条轻边上的两个节点一定包含在两条重链中。例如轻边1-3，节点分别包含于重链1-2-5-7和重链3-6中。

现在假设需要对任意两点u、v之间的路径进行处理，例如，我们需要将u、v路径上所有节点权值求和。我们可以分别处理u-lca(u,v),v-lca(u,v)，根据性质3，路径最多分为logn条重链和轻边。u-v上的所有节点包含于其中。

（1）对于重链，由于其时间戳连续，相当于一个序列，可以用线段树（或其他数据结构）维护。

（2）对于轻边，可以跳过，因为轻边的两个端点包含在2条重链之中。

如何实现轻/重链划分？

我们需要维护以下信息：

（1）size[x]:以x为根的子树节点个数。

（2）son[x]:以x为根的子树，x的重儿子。

（3）father[x]:x节点的父亲

（4）deep[x]:x节点的深度

（5）top[x]:x节点所在重链的起始节点。

（6）id[x]:x节点的访问次序（优先访问重儿子），代表了其在线段树中的位置

（7）s[i]:线段树中位置[i,i]的节点对应树中哪个节点。s[id[x]]=x.

我们可以通过两次dfs完成上述信息的维护，参考代码如下：

图3

第1次dfs结束维护信息如下图：

图4 图5

第2次dfs结束维护信息如下图：

图6

如何寻找u、v的lca?

（1）如果top[u]=top[v]，说明u，v在一条重链上，那么lca(u,v)为u、v深度较小的点。假设深度较小的点是u，u到v路径对应了线段树上的一段区间[id[u],id[v]]。

（2）如果top[u]!=top[v]，说明u、v在不同重链上，他们的lca可能在其中一条重链上，也可能在其它重链上。假设top[u]深度>top[v]，那么lca(u,v)一定不会在top[u]上，u可以跳转到father[top[u]]，跳过的这一段重链对应了线段树上的一段区间[id[top[u]],id[u]]；u、v交替跳转最终如果top[u]==top[v]，回到（1），问题得解。

参考代码如下，函数ask询问u、v两点路径上节点的权值和，query函数是查询线段树的区间和，线段树部分此处省略。

图7

参考练习题目：

ybt1560-1564