将一棵树进行重链剖分:
表示一下各链的父子关系:
就像倍增求 lca 一样, 以节点 (链) 的向上 jump 来求 lca.
当要求的两点在同一条链上时, lca 就是深度较浅的那个点.
当要求的两点在不同的两条有祖先后代关系的两条链上时, lca 就是深度较浅的那条链的链与较深的那条链的交汇点与深度较浅的那个点的深度较浅者.
当要求的两点在不同的两条没有祖先后代关系的两条链上时, lca 就是这两条链与它们的 lca 的交汇点的深度较浅者.
后记:
回想一下 lca 的暴力求法: 两个点在两条一定会交汇的长链上同时向上跳跃.
用树链剖分求 lca, 可以看作对暴力的优化.
来源: http://www.bubuko.com/infodetail-3121664.html