最近公共祖先(LCA) - riteme.site

[riteme]

https://riteme.github.io/blog/2016-2-1/lca.html

[ghost]

哇！前排膜一个，谢谢大佬的讲解Orz

[eqvpkbz]

$2 ^ 2 = (10)_2$

这句话有问题吧，不应该是

$2 ^ 2 = (100)_2$

[riteme]

@eqvpkbz 多谢指出，已经修改。

[gitusercake]

最后一张图可能有点问题： distance=6 f[u,1],f[v,1]都应该改成f[u,0],f[v,0]

[riteme]

@gitusercake

应该没有画错。原意是跳到LCA下面的一个点，所以距离是5

[ghost]

请问 LCA(x, y) = LCA(y, x) = ancestor[x] 这一句是否应该改成 LCA(x, y) = LCA(y, x) = ancestor[find(x)]，实际测试无法通过

[riteme]

@VecTest

你说的对。错的挺明显的 QAQ

现在已经修正了