标签:倍增

1 篇文章

详解使用 Tarjan 求 LCA 问题(图解)
LCA问题有多种求法,例如倍增,Tarjan。 本篇博文讲解如何使用Tarjan求LCA。 如果你还不知道什么是LCA,没关系,本文会详细解释。 在本文中,因为我懒为方便理解,使用二叉树进行示范。 LCA是什么,能吃吗? LCA是树上最近公共祖先问题。 最近公共祖先就是树上有两个结点,找一个结点,是他们的公共祖先,并且离他们两个结点最近。 例如这是…