一般来讲，我们很熟悉序列的操作，对于树上路径的操作会觉得比较棘手。而树链剖分基本思想，是将树上的路径问题转化为序列操作问题。
树链剖分，简单来讲即将一棵树划分为若干条链，然后用数据结构去维护每一条链。
常见的树链剖分方法为轻/重划分。
相关概念
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.如果(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，优先访问每个节点的重儿子，并按照每个节点的发现时间为其盖上时间戳。如下图：
我们可以观察到两个特征：
（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完成上述信息的维护，参考代码如下：
第1次dfs结束维护信息如下图：
第2次dfs结束维护信息如下图：
如何寻找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函数是查询线段树的区间和，线段树部分此处省略。
参考练习题目：
ybt1560-1564
