Open ManuShi98 opened 1 year ago
https://manushi98.github.io/2017/11/08/POJ%20-%201330%20Nearest%20Common%20Ancestors(%E5%80%8D%E5%A2%9ELCA)/
思路在有根树中，我们称距离u和v所有公共祖先中距离最近的称为最近公共祖先(LCA)。一个朴素的求u和v的LCA的想法是让u和v先深度相同，然后逐层向上直到碰到相同元素。复杂度为O(n)。虽然看着简单有效，但对多次查询来说这个复杂度十分不友好。为了高效求解公共祖先，我们有三种方式： 倍增法（在线，实现简单） RMQ（在线，实现复杂） Tarjan（离线） 本题我们使用倍增法求LCA。倍增法构
https://manushi98.github.io/2017/11/08/POJ%20-%201330%20Nearest%20Common%20Ancestors(%E5%80%8D%E5%A2%9ELCA)/
思路在有根树中，我们称距离u和v所有公共祖先中距离最近的称为最近公共祖先(LCA)。一个朴素的求u和v的LCA的想法是让u和v先深度相同，然后逐层向上直到碰到相同元素。复杂度为O(n)。虽然看着简单有效，但对多次查询来说这个复杂度十分不友好。为了高效求解公共祖先，我们有三种方式： 倍增法（在线，实现简单） RMQ（在线，实现复杂） Tarjan（离线） 本题我们使用倍增法求LCA。倍增法构