树链剖分

基础概念
重儿子：父节点的所有儿子中子树节点数目最多的节点
轻儿子：父节点除重儿子以外的节点
重边：父节点和重儿子连成的边
轻边：父节点和轻儿子连成的边
重链：由多条重边连接而成的路径
如下图，绿色边即为重边

性质
1.整棵树会被剖分成若干条重链（可以将单独的叶子节点看作一条重链）
2.轻儿子一定是每条重链的顶点
3.任意一条路径被切分成不超过 \(\log n\) 条链

相关资料