最近两天写了几道树链剖分，终于能够写出一个两百行的程序不用陷入无尽调试了。

树链剖分需要对于每个点求出如下几个域：

dep：此点深度

siz:此点子树的点数

fa：此点的父亲

son：此点重儿子的编号

top：此点所在重链顶端的点编号

w：如果题目要维护的权值在点上：表示此点在所在重链中的编号

   如果题目要维护的权值在边上：表示此点与其父亲的连边在其所在重链中的编号

belong：此点（或此点与其父亲的连边）所属重链的编号

weight：此点（或此点与其父亲的连边）的权值

-----------------------------------------------------------------------------

这些东西的求出可以用两次DFS求，也可以用一次BFS生成BFS序列，再对序列正反两次扫描得到。但是由于树链剖分的题点数较大，DFS可能爆栈，故推荐BFS方法。

-----------------------------------------------------------------------------

对于每一条重链可以用线段树维护，但需要考虑空间消耗问题。也可以把所有的链放在一个线段树里维护，但是会加大常数。

-----------------------------------------------------------------------------

对于一个查询(u,v)来说，可以先求LCA再逐步提升两个点，也可以这么做：

令f1=top[u],f2=top[v]，如果f1==f2那么两个点已经在一条链上，链内查询；否则不妨设dep[f1]<=dep[f2]，则先链内查询将v提至f2,然后通过一条轻边将f2提至fa[f2]，重复此过程。

这么做最后两个点一定都停在他们的LCA处，因此树链剖分也可以用来在线求LCA，每一条重链不加任何数据结构维护，空间消耗O(n)。

----------------------------------------------------------------------------

永远不要用std::vector来存储边。

----------------------------------------------------------------------------

树链剖分一般长度会有150+。但是写熟之后就没什么感觉了。

----------------------------------------------------------------------------

END。