数据结构与算法_树链剖分
树链剖分的思想是通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链（线性结构），然后再通过数据结构（如树状数组， SBT，splay，线段树等）来维护每一条链。即非线性结构转变为线性结构。
树链剖分可以维护树上路径信息，每条重链就相当于一段区间，用数据结构去维护。把所有的重链首尾相接，放到同一个数据结构上，然后维护这一个整体即可。
树链剖分的用处比倍增多，倍增能做的题树剖一定能做，反过来则否。树链剖分的代码复杂度不算特别高，调试也不难。
树链剖分支持以下操作：
如何划分树链？
重要性质：
若 v 是轻儿子， u 是 v 的父亲， 则有 size[v] <= size[u] / 2;
从根到某一点的路径上， 不超过 log2n条重链，不超过 log2n 条轻边。
